1258 - Making Huge Palindromes

Problem Link: http://lightoj.com/volume_showproblem.php?problem=1258

Solution idea :

Consider the 4th test case
P = anncbaaababaaa
Let
Q = aaababaaabcnna (reverse of P)
Now look how can we construct the shortest palindrome by adding character to the
right of P,
with the help of Q
P : anncbaaababaaa|||||
Q : |||||aaababaaabcnna
Ans:anncbaaababaaabcnna
So all we need to do is search for the longest prefix of Q in P.
You can do this by using KMP.

Solution :

#include<bits/stdc++.h>

using namespace std;

int f[1000002];

void kmp_preprocess(string pattern)
{
    int m=pattern.size();
    f[0]=0;

    int j=0;

    for(int i=1;i<m;i++)
    {
        if(pattern[i]==pattern[j])
        {
            f[i]=j+1;
            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];
                if(pattern[i]==pattern[j])
                {
                    f[i]=j+1;
                    j++;
                    break;
                }
            }
        }
    }
}

int kmp(string text,string pattern)
{
    int j=0;

    int n=text.size();
    int m=pattern.size();

    for(int i=0;i<n;i++)
    {
        if(text[i]==pattern[j])
        {

            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];

                if(text[i]==pattern[j])
                {
                    j++;
                    break;
                }
            }
        }
    }
    return j;
}


int main()
{

string text,pattern;

 int n,p,q;
 scanf("%d",&n);

 for(int ca=1;ca<=n;ca++)
 {
     cin>>text;

     pattern=text;
     reverse(pattern.begin(),pattern.end());
     memset(f,0,sizeof(f));
    kmp_preprocess(pattern);

     p=kmp(text,pattern);
     q=pattern.size();
     q=2*q - p ;
     printf("Case %d: %d\n",ca,q);
 }


}

1255 - Substring Frequency / kmp source code 2

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1255

Solve :

#include<bits/stdc++.h>
#define ll long long

using namespace std;

ll int f[1000003];

void kmp_preprocess(string pattern)
{
    ll int m=pattern.size();
    f[0]=0;

    ll int j=0;

    for(ll int i=1;i<m;i++)
    {
        if(pattern[i]==pattern[j])
        {
            f[i]=j+1;
            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];
                if(pattern[i]==pattern[j])
                {
                    f[i]=j+1;
                    j++;
                    break;
                }
            }
        }
    }
}

ll int  kmp(string text,string pattern)
{
   ll int j=0,cnt=0;

    ll int n=text.size();
    ll int m=pattern.size();

    for(ll int i=0;i<n;i++)
    {
        if(text[i]==pattern[j])
        {
            j++;
            if(j==m)
            {
                cnt++;
                j=f[j-1];
            }

        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];

                if(text[i]==pattern[j])
                {
                    j++;
                    break;
                }
            }
        }
    }
    return cnt;
}


int main()
{
   string text,pattern;
   ll int t,n=0;
   scanf("%lld",&t);

for(ll int ca=1;ca<=t;ca++)
{
      cin>>text>>pattern;
      memset(f,0,sizeof(f));
      kmp_preprocess(pattern);
      n=kmp(text,pattern);
      printf("Case %lld: %lld\n",ca,n);

}

}

10679 - I Love Strings!!

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1620

Solution :

#include<bits/stdc++.h>

using namespace std;

int f[1000000];

void kmp_preprocess(string pattern)
{
    int m=pattern.size();
    f[0]=0;

    int j=0;

    for(int i=1;i<m;i++)
    {
        if(pattern[i]==pattern[j])
        {
            f[i]=j+1;
            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];
                if(pattern[i]==pattern[j])
                {
                    f[i]=j+1;
                    j++;
                    break;
                }
            }
        }
    }
}

bool kmp(string text,string pattern)
{
    int j=0;

    int n=text.size();
    int m=pattern.size();

    for(int i=0;i<n;i++)
    {
        if(text[i]==pattern[j])
        {
            if(j==m-1) return true;
            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];

                if(text[i]==pattern[j])
                {
                    j++;
                    break;
                }
            }
        }
    }
    return false;
}


int main()
{

   int k,q;

   scanf("%d",&k);
   string text,pattern;

   while(k--)
   {
      cin>>text;

       scanf("%d",&q);

       while(q--)
       {
           cin>>pattern;
           kmp_preprocess(pattern);

            bool n;

          n=kmp(text,pattern);

          if(n==1) cout<<"y"<<endl;
          else cout<<"n"<<endl;

       }
   }


}

KMP source code 1

Tutorial :

1. https://tanvir002700.wordpress.com/2015/03/03/kmp-knuth-morris-pratt-algorithm/#more-556

2. https://returnzerooo.wordpress.com/2016/09/08/kmp/

3. https://www.youtube.com/watch?v=GTJr8OvyEVQ

4. https://www.youtube.com/watch?v=KG44VoDtsAA



source code :

#include<bits/stdc++.h>

using namespace std;

int f[1000000];

void kmp_preprocess(string pattern)
{
    int m=pattern.size();
    f[0]=0;

    int j=0;

    for(int i=1;i<m;i++)
    {
        if(pattern[i]==pattern[j])
        {
            f[i]=j+1;
            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];
                if(pattern[i]==pattern[j])
                {
                    f[i]=j+1;
                    j++;
                    break;
                }
            }
        }
    }
}

bool kmp(string text,string pattern)
{
    int j=0;

    int n=text.size();
    int m=pattern.size();

    for(int i=0;i<n;i++)
    {
        if(text[i]==pattern[j])
        {
            if(j==m-1) return true;
            j++;
        }
        else
        {
            while(j!=0)
            {
                j=f[j-1];

                if(text[i]==pattern[j])
                {
                    j++;
                    break;
                }
            }
        }
    }
    return false;
}


int main()
{
   string text,pattern;

   cin>>text>>pattern;

    kmp_preprocess(pattern);

    bool n;

    n=kmp(text,pattern);

    cout<<n;

}