CF 149E Martian Strings（KMP）

链接：

http://codeforces.com/problemset/problem/149/E

题目大意：

给出字符串S， 然后再给m个字符串T，判断有几个T是可以在S中找到坐标a,b,c,d, (1 ≤ a ≤ b < c ≤ d ≤ n),使得S【a...b】+S【c...d】 = T.

分析与总结：

先找T的前缀，要找所有长度的前缀的最后一个字母在S中第一次出现的位置，这个过程只需要进行一次KMP运算便可以保存下来。

然后就是把寻找后缀，把S和T都逆序存好，再进行一次KMP运算找后缀，看是否可以找到一个长度为x的后缀的位置在一个长度为len-s的前缀（如果存在）位置之后，如果可以找到就可判断这个T可以有S中的组成。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 100005;
char S[MAXN], T[1005];
char str[MAXN];
int  Right[MAXN]; // 各个长度的前缀的尾部最左边的那个位置
int  next[MAXN];

void getNext(char* P,int* f){
    int m=strlen(P);
    f[0] = f[1] = 0;
    for(int i=1; i<m; ++i){
        int j=f[i];
        while(j && P[i]!=P[j]) j=f[j];
        f[i+1] = P[i]==P[j]?1+j:0;
    }
}

bool find(char* S,char* T,int* f,int flag){
    getNext(T,f);
    int n=strlen(S);
    int m=strlen(T);
    int j=0;
    for(int i=0; i<n; ++i){
        while(j && S[i]!=T[j]) j=f[j];
        if(S[i]==T[j]) ++j;
        if(flag==1 && j && Right[j]==-1){
            Right[j] = i;
        }
        else if(flag==2){
            if(j && Right[m-j]!=-1 && Right[m-j]<n-i-1){
                return true;
            }
        }
    }
    return false;
}

void rev(char* S,int len){
    char ch;
    for(int i=0,k=len-1; i<len/2; ++i,--k){
        ch=S[i]; S[i]=S[k]; S[k]=ch;
    }
}
void revcpy(char* S,char* str,int len){
    for(int i=len-1, k=0; i>=0; --i){
        str[k++] = S[i];
    }
    str[len] = '\0';
}

int main(){
    int m;
    scanf("%s",S);
    scanf("%d",&m);
    int cnt=0;
    while(m--){
        scanf("%s",T);
        memset(Right, -1, sizeof(Right));
        find(S,T,next,1);
        revcpy(S,str,strlen(S));
        rev(T,strlen(T));
        if(find(str,T,next,2)) 
            ++cnt;
    }
    printf("%d\n",cnt);
    return 0;
}

—— 生命的意义，在于赋予它意义士。

原创http://blog.csdn.net/shuangde800，By D_Double (转载请标明)