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\n", find(S,S2,f,2));
    }
    return 0;
}

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

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