XDU 1154 大黄的选票(KMP)
题目:
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了一个晚上...)。
代码:
[cpp]
#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;
}
补充:综合编程 , 其他综合 ,