Codeforces149E - Martian Strings(KMP)

제목 의 대의
문자열 T 를 지정 합 니 다. 다음은 n 개의 문자열 이 있 습 니 다. 각 문자열 S 에 대해 T [a... b] + T [c.. d] = S (1   ≤   a   ≤   b   <   c   ≤   d   ≤   length (T)) 가 존재 하 는 지 판단 합 니 다.
해제
모든 문자열 S 에 대해 우 리 는 문자열 T 에 순서대로 일치 하고 S 의 모든 문자 가 T 에 처음 일치 하 는 위치 (배열 pos 로 기록 하 는 것 을 가정) 를 기록 한 다음 에 문자열 T 와 S 를 역 순 으로 한 다음 에 S 로 T 에 일치 합 니 다. 현재 S 가 i 에 일치 하고 문자열 T 의 위 치 는 j, S 의 i + 1 문자 가 원래 문자열 의 위 치 는 length 라 고 가정 합 니 다.(S) - i - 2, T 문자열 의 j 번 째 문 자 는 원래 문자열 의 위치 가 length (T) - j - 1 이 며, pos [length (S) - i - 2] < length (T) - j - 1 이면 조건 에 부합 합 니 다.
코드:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define MAXN 1005

char p[MAXN],T[MAXN*100];

int f[MAXN],pos[MAXN],ans;

void getfail()

{

    int j,len=strlen(p);

    f[0]=j=-1;

    for(int i=1;i<len;i++)

    {

        while(j>=0&&p[j+1]!=p[i]) j=f[j];

        if(p[j+1]==p[i]) j++;

        f[i]=j;

    }

}

void find(int d)

{

    int j=-1,lent=strlen(T),lenp=strlen(p);

    for(int i=0;i<lent;i++)

    {

        while(j>=0&&p[j+1]!=T[i]) j=f[j];

        if(p[j+1]==T[i]) 

        {

            j++;

            if(!d&&pos[j]==-1) pos[j]=i;

            if(d)

            {

                if(lenp-j-2>=0&&pos[lenp-j-2]!=-1)

                {

                    if(pos[lenp-j-2]<lent-i-1)

                    {

                        ans++;

                        break;

                    }

                }

            }

        }

        if(!d&&j+1==lenp) break;

    }

}

int main()

{

    int n;

    scanf("%s",T);

    scanf("%d",&n);

    ans=0;

    for(int i=0;i<n;i++)

    {

        memset(pos,-1,sizeof(pos));

        scanf("%s",p);

        getfail();

        find(0);

        reverse(p,p+strlen(p));

        reverse(T,T+strlen(T));

        getfail();

        find(1);

        reverse(T,T+strlen(T));

    }

    printf("%d
",ans);

    return 0;

}