XDU 1154 대황 표 (KMP)

링크:
http://acm.xidian.edu.cn/land/problem/detail?problem_id=1154
제목:
Description
학교 에서 유기 견 을 쫓 아야 하 는 이 유 는 '장엄 하 다' 는 한 표를 던 지라 고 한 선거 에서 서 전대 황 을 뽑 는 유권자 가 너무 많아 서...
유사 한 상황 이 재발 하지 않도록 학교 에 서 는 새로운 투표 방법 을 채택 하기 로 했다.
1. 표 에 한 글자 만 쓸 수 있 습 니 다!
2. 특정한 순서 (예 를 들 어 주민등록번호) 에 따라 표를 S 줄 로 배열 한다.
3. 각 선거인 은 두 개의 꼬치 s1, s2 에 대응한다.
4. 표를 찍 을 때 S 를 옮 겨 다 니 는 모든 꼬치 S' 는 S' 가 s1 로 시작 하고 s2 로 끝 나 는 경우 (s1, s2 가 겹 칠 수 있 음) 해당 하 는 피선거자 한 표 라 고 할 수 있다.
5. 만약 에 어떤 꼬치 가 여러 명의 피 선거인 에 게 동시에 효과 가 있다 면 이 몇 명 은 모두 한 표 라 고 할 수 있다.
6. 득 표 가 많 을 수록 좋다
그래.. 사실 너무 깊이 알 필 요 는 없어. 우 리 는 대황 이 새로운 투표 방법 에서 얼마나 많은 표를 얻 을 수 있 는 지 에 만 관심 이 있어..
Input
다 중 그룹 데이터.
각 그룹의 데이터 3 줄 은 각각 S, s1, s2 이 고 의 미 는 상기 와 같다.
0<|S|,|s1|,|s2|<=10000;모든 문자열 은 소문 자 만 포함 합 니 다.
Output
각 조 는 한 줄 을 출력 하고 하나의 정 수 를 포함 하여 마지막 표 수 를 표시 합 니 다.
Sample Input
dahuangg
d
g
ggnauhad
d
g
Sample Output
2
0
분석 과 총 결:
1. S1 이 원래 문자열 에 있 는 모든 일치 하 는 위치 i 를 찾 아 dp [i] 에 기록 한 다음 dp 배열 에 따라 dp [i] 를 계산 하여 모든 i 이전의 S1 이 몇 개 인지 표시 합 니 다.상태 이동: dp [i] = dp [i] + dp [i - 1].
2. 그 다음 에 KMP 로 S2 를 매 칭 합 니 다. S2 를 찾 을 때마다 위치 가 i 라 고 가정 하면 j = = m (S2 와 일치 합 니 다) 를 발견 합 니 다. 이것 은 i 가 S2 의 꼬리 위치 입 니 다. 이때 i 전에 S1 이 몇 개 있 는 지 찾 아야 합 니 다. 즉, dp [i] 를 추가 하면 됩 니 다.그런데 여기 문제 가 있어 요. 주의해 야 돼 요!S' 는 s1 로 시작 하여 s2 로 끝 납 니 다 (s1, s2 는 겹 칠 수 있 습 니 다). 즉, S1 이 S2 보다 길이 가 짧 으 면 dp [i] 안에 S1 이 S2 에 포함 되 어 있 을 수 있 습 니 다. 이것 은 S1 로 시작 하 는 것 이 아 닙 니까?그래서 이 단 계 는 따로 토론 해 야 한다.(이 문제 로 밤새 WA...)
코드:

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

typedef long long int64;
const int MAXN = 20005;
char S[MAXN];
char S1[MAXN],S2[MAXN];
int  f[MAXN];
int  len1;
int64  dp[MAXN];

void getFail(char* P,int* f){
    int n=strlen(P);
    f[0]=f[1]=0;
    for(int i=1; i<n; ++i){
        int j=f[i];
        while(j && P[i]!=P[j]) j=f[j];
        f[i+1] = P[i]==P[j]?1+j:0;
    }
}
int64 find(char* S,char* T,int* f,int flag){
    getFail(T,f);
    int n=strlen(S);
    int m=strlen(T);
    int j=0;
    int64 cnt=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==m){
            ++dp[i];
        }
        else if(flag==2 && j==m){
            if(len1>=m)  //             
                cnt += dp[i];
            else{
                cnt += dp[i-(m-len1)];
            }
        }
    }
    return cnt;
}

int main(){
    while(scanf("%s %s %s",S,S1,S2)!=EOF){
        memset(dp, 0, sizeof(dp));
        find(S,S1,f,1);
        for(int i=1; S[i]; ++i)
            dp[i] += dp[i-1];
        len1=strlen(S1); // S1   
        printf("%lld
", find(S,S2,f,2));
    }
    return 0;
}

- 생명의 의 미 는 의 미 를 부여 하 는 데 있다.
오리지널 http://blog.csdn.net/shuangde800, By DDouble (전재 표시)