当前位置:编程学习 > 网站相关 >>

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; 

 

补充:综合编程 , 其他综合 ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,