poj(1226)KMP

题意：给n个字符串，求最长的一个字符串s使得给出的n个字符串中都会出现s或者s的反转。

解法：KMP裸题，枚举第一个串的所有子串对其他所有串进行KMP。

代码：

/****************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>

using namespace std;

#define eps 1e-8
typedef long long LL;



int n;
string s[110];
int next1[110];
int next2[110];
string tool1;
string tool2;
void getNext1(int l,int r)
{
    tool1=s[0].substr(l,r-l+1);
   int i=0;
   int j=-1;
   next1[0]=-1;
   while(i<tool1.size())
   {
       while(j!=-1&&tool1[i]!=tool1[j]) j=next1[j];
       next1[++i]=++j;
   }
}
void getNext2(int l,int r)
{
    tool2=tool1;
    reverse(tool2.begin(),tool2.end());
   int i=0;
   int j=-1;
   next2[0]=-1;
   while(i<tool2.size())
   {
       while(j!=-1&&tool2[i]!=tool2[j]) j=next2[j];
       next2[++i]=++j;
   }
}
bool OK1(int k)
{
    //cout<<tool1<<endl;
    int j=0;
    for(int i=0;i<s[k].size();i++)
    {
        if(s[k][i]==tool1[j])
            j++;
        else
        {
            if(j==0)
                continue;
            j=next1[j];i--;
        }
        if(j==tool1.size())
            return true;
    }
    return false;
}
bool OK2(int k)
{
    int j=0;
    for(int i=0;i<s[k].size();i++)
    {
        if(s[k][i]==tool2[j])
            j++;
        else
        {
            if(j==0)
                continue;
            j=next2[j];i--;
        }
        if(j==tool2.size())
            return true;
    }
    return false;
}
int main()
{
    int  t;
    cin>>t;
    while(t--)
    {
        scanf("%d",&n);
        for(int i=0; i<n; i++)
            cin>>s[i];
        int ans=0;
        for(int i=0; i<s[0].size(); i++)
        {
            for(int j=i; j<s[0].size(); j++)
            {
              getNext1(i,j);
              getNext2(i,j);
              bool flag=1;
              for(int k=1;k<n;k++)
              {
                  if(!OK1(k)&&!OK2(k))
                    {
                        flag=0;
                        break;
                    }
              }
              if(flag)
                ans=max(ans,j-i+1);//cout<<tool<<" "<<i<<" "<<j<<" "<<next1[0]<<" "<<next1[1]<<" "<<next1[2]<<endl;
            }
        }
        cout<<ans<<‘\n‘;
    }
    return 0;
}

poj(1226)KMP,布布扣,bubuko.com

poj(1226)KMP

原文：http://blog.csdn.net/xiefubao/article/details/24319397