XDU 1154大黄の票(KMP)

リンク:
http://acm.xidian.edu.cn/land/problem/detail?problem_id=1154
タイトル:
Description
学校が放浪犬を駆除する理由は、ある「荘厳」の一票を投じる選挙で、西電大黄を選ぶ有権者が多すぎるからだという.
このようなことが二度と起こらないように、学校は新しい投票方法を採用することにしました.
1.投票用紙に文字を書くだけです.
2.ある順番(例えば、身分証番号)で、票をS列に並べる.
3.各被選挙人は二つの串s 1に対応しています.s 2
4.チケットを注文する時、Sの各サブストリングS'を遍歴して、S'がs 1で始まるなら、s 2は終わる(s 1、s 2は重複することができます)、対応する被選挙人の1票を計算します.
5.ある子が同時に複数の被選挙人に有効であれば、この数人は一票としてカウントされます.
6.得票が多ければ多いほどいいです
はい、あまり深く知る必要はないです.黄さんは新しい投票方法の中でどれぐらいのチケットを手に入れられますか?
Input
複数グループのデータ
各グループのデータは3行、それぞれの行はS、s 1、s 2であり、上記のように意味がある.
0<|S 124;、124; s 1𞓜、124; s 2𞓜<=10000;すべての文字列には小文字だけが含まれています.
Output
各グループは1行を出力して、1つの整数を含んで最後の切符の数を表します.
Sample Input
dahuang gg
d
g
gnauhad
d
g
Sample Output
2
0
分析とまとめ:
1.まずS 1を探して、元の文字列の中の全ての整合位置iをdp【i】に記録し、dp配列からdp[i]を計算して、すべてのiの前のS 1がいくつあるかを表します.状態移行:dp[i]=dp[i]+dp[i-1]
2.そしてKMPマッチS 2を使用して、S 2が見つかった時に、位置がiであると仮定して、j==m(S 2にマッチした)を発見しました.これはiがS 2の末尾の位置です.ここでiを探す前にS 1がいくつありますか?すなわちdp【i】を加えるだけでいいです.しかし、ここに問題があります.注意してください.S'はs 1で始まり、s 2で終わっています.つまり、S 1がS 2より短いと、dp[i]の中にS 1がS 2に含まれている場合があります.これはS 1で始まるのではありません.ですから、このステップは別々に検討します.(この問題で一晩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 D_Double(転載は明記してください)