OJ Board

Code: Select all

Accepted... silly index error.  Thanks!

Code: Select all

#include<iostream>
#include<stack>

using namespace std;

char text[100001], pat[100001];
int f[100001];
stack<char> tempS;

bool isPalindrome(char* T)
{
    int i;
    for(i=0;i<strlen(T)/2;i++)
        if(T[i]!=T[strlen(T)-1-i])
            return false;
    return true;
}

void reverse(char T[], char* P)
{
    int i;
    char temp;
    for(i=0;i<strlen(T);i++)
        P[strlen(T)-1-i]=T[i];
    P[strlen(T)]='\0';
}

void fFunction(char*P)
{
	int i,j,m;
	i=1;
	j=0;
	m=strlen(P);
	while(i<=m-1)
	{
		if(P[j]==P[i])
		{
			f[i]=j+1;
			i++;
			j++;
		}
		else if(j>0)
			j=f[j-1];
		else
		{
			f[i]=0;
			i++;
		}
	}
}

void KMPMatch(char* T, char*P)
{
    bool done=false;
	int i,j,m,trace=0,k;
	i=0;
	j=0;
	while(i<=strlen(T) && !done)
	{
       	m=strlen(P);
		if(P[j]==T[i])
		{
			if(j==m-1)
			{

                cout<<text;
                while(!tempS.empty())
                {
                    cout<<tempS.top();
                    tempS.pop();
                }
                cout<<endl;              
                done=true;
            }
			i++;
			j++;
		}
		else if (j>0)
		{
			trace=j;
			j=f[j-1];
			for(k=0;k<trace-j;k++)
			{
			    tempS.push(P[strlen(P)-1]);
			    P[strlen(P)-1]='\0';
            }
        }
		else
		{
			i++;
			tempS.push(P[strlen(P)-1]);
			P[strlen(P)-1]='\0';
        }
    }
}

int main()
{
	int i;
	while(cin>>text)
	{
        if(isPalindrome(text))
          cout<<text<<endl;
        else
        {
           reverse(text,pat);
    	   fFunction(pat);
	       KMPMatch(text,pat);
        }
    }
	return 0;
}