专栏首页wymHDU 6629 (2019杭电第五场 1006) string matching (扩展kmp)

HDU 6629 (2019杭电第五场 1006) string matching (扩展kmp)

题意: 求字符串 s[i…len−1] and s[0…len−1] i>0 最长公共前缀长度求解过程的比较次数

题解: 当时一看就直接AC自动机然后用fail指针就行,结果输入字符是ASCII那就超内存了。用扩展kmp求出每一个后缀的最长公共前缀求和即可。注意 当前下标加上最长前缀长度超过字符串长 ans--。 因为是求比较次数。

扩展KMP解决的问题:

定义母串S和子串T,S的长度为n,T的长度为m;

求 字符串T 与 字符串S的每一个后缀 的最长公共前缀;

也就是说,设有extend数组:extend[i]表示T与S[i,n-1]的最长公共前缀,要求出所有extend[i](0<=i<n)。

设有辅助数组next[i]表示T[i,m-1]和T的最长公共前缀长度

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int K=1000005;
int nt[K],extand[K];
char S[K],T[K];
int a[K];
ll ans;
void Getnext(char *T,int *next)
{
    int len=strlen(T),a=0;
    next[0]=len;
    while(a<len-1 && T[a]==T[a+1]) a++;
    next[1]=a;
    a=1;
    for(int k=2; k<len; k++)
    {
        int p=a+next[a]-1,L=next[k-a];
        if( (k-1)+L >= p)
        {
            int j = (p-k+1)>0 ? (p-k+1) : 0;
            while(k+j<len && T[k+j]==T[j]) j++;
            next[k]=j;
            a=k;
        }
        else
            next[k]=L;
    }
}
void GetExtand(char *S,char *T,int *next)
{
    Getnext(T,next);
    int slen=strlen(S),tlen=strlen(T),a=0;
    int MinLen = slen < tlen ? slen : tlen;
    while(a<MinLen && S[a]==T[a]) a++;
    extand[0]=a;
    a=0;
    for(int k=1; k<slen; k++)
    {
        int p=a+extand[a]-1, L=next[k-a];
        if( (k-1)+L >= p)
        {
            int j= (p-k+1) > 0 ? (p-k+1) : 0;
            while(k+j<slen && j<tlen && S[k+j]==T[j]) j++;
            extand[k]=j;
            a=k;
        }
        else
            extand[k]=L;
    }
}
//以上是模版
int main(void)
{
	int tl;scanf("%lld",&tl);
    while(tl--)
    {
    	memset(nt,0,sizeof(nt));
    	memset(extand,0,sizeof(extand));
    	memset(a,0,sizeof(a));
		scanf("%s",S);
    	ans = 0;
    	strcpy(T,S);
        GetExtand(S,T,nt);
        int len = strlen(T);
        queue<int> id;
		ans = 0;
		ans+=len-1;
		for(int i=1; i<len; i++) {
			if(nt[i]!=0) {
				ans+=nt[i];
				if(i+nt[i]>=len)ans--;
			}
		}
		printf("%lld\n",ans);
    }
    return 0;
}
/*
3
_Happy_New_Year_
ywwyww
zjczzzjczjczzzjc

17
7
32
*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 模板--LIS

    用户2965768
  • P3834 【模板】可持久化线段树 1(主席树) (多次查询第k大或第k小)

    用户2965768
  • HDU 6370 Werewolf(并查集+dfs) 18年暑假多校赛第六场

    讲解博客:http://www.cnblogs.com/curieorz/p/9447454.html

    用户2965768
  • KMP专题

    POJ 2406 Power Strings http://poj.org/problem?id=2406 题意:找出s字符窜由多少个重复子窜循环构成 分析:K...

    用户1624346
  • 【AtCoder - 2300】Snuke Line(树状数组)

    每隔d站停一次的列车,一定能买到购买区间的长度≥d的纪念品。 长度比d小但包含了d的倍数的纪念品也可以买到。 所以,如果按长度给纪念品排序,用树状数组维护长...

    饶文津
  • 和为0的最长连续子数组【转载+优化代码】

    题目描述和思路来自博客:http://www.cnblogs.com/coding-wtf/p/5849222.html,在此表示感谢。

    xiaoxi666
  • 算法细节系列(19):广度搜索优先

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 2019河南科技学院发现杯

    来到学校后第一次参加算法比赛,听学长说去年的难度非常高,所以这次比赛目标就是得到分数。但今年的难度整体偏低,第八题做的比较懵,第十题不会做(连题都看不懂 ),其...

    dejavu1zz
  • AtCoder Beginner Contest 173 A ~ F(已经补完)

    C 思路:二进制枚举 for(int i=0;i<(1<<h);i++) for(int j=0;j<(1<<w);j++) 二进制每次+1就可以暴力遍...

    用户7727433
  • 挑战程序竞赛系列(95):3.6数值积分(1)

    挑战程序竞赛系列(95):3.6数值积分(1) 传送门:AOJ 1313: Intersection of Two Prisms 题意: 有一个侧棱与Z轴平行...

    用户1147447

扫码关注云+社区

领取腾讯云代金券