注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

扩展kmp  

2016-08-11 19:39:30|  分类: 算法&数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
        下面是裸题:
        求字符串S与 字符串T所有后缀 的 最长公共前缀(以下缩略为最长前缀)。
=======================================
        刚开始写这个的时候,也是有点忘蛤~
        首先呢,这个算法既然叫扩展kmp那就和kmp很像,先求出字符串T与 它本身所有后缀 的最长前缀。首先少不了的是next数组的定义了:next[i]=T[i~n-1]与T[0~n-1]的最长前缀,但是求出next数组的方法又跟manacher很像。
         所以,是要先学kmp和manacher,再学扩展kmp比较好神犇请忽略
        好了,现在就开始讲如和next数组。
        首先,和manacher类似,也有一个最远延伸,借助最远延伸求出全部或部分答案,然后更新延伸,假如当前要求next[i],那么最远延伸u=p+next[p](p=0~i-1),这个可以有现在可以自己想想如何 借助最远延伸求出全部或部分答案,然后更新延伸。
        重点:
扩展kmp - 杨鸿飞 - 杨鸿飞的博客
        nx=next

        那么可以直接求出的部分就是next[i-p]因为T[i~p+next[p]-1]=T[0~next[p]-1],求不出的部分就可以从u开始暴力求,特别的,next[0]=n,next[1]暴力求。
        对于求S与 T所有后缀 的最长前缀,也需要一个数组ex,ex[i]=S[0~n-1]与T[i~n-1]的最长前缀,方法和前面是差不多的。
=======================================
模板:

#include <algorithm>
#include <iostream>
#include <string>
#include <cstdio>

using namespace std;

const int ML=100000;

string S,T;

int next[ML+10],ex[ML+10];

int main()
{
cin>>S>>T;

int lens=S.size(),lent=T.size();

/*===================求next=====================*/

next[0]=lent;

for (int i=0; i<lent-1; i++) //暴力求
if (T[i]==T[i+1]) next[1]++;
else break;

int p=1;

for (int i=2; i<lent; i++)
{
int u=p+next[p];

if (i+next[i-p]<u) next[i]=next[i-p]; //全部答案
else //部分答案
{
int j=max(u,i);

for ( ; j<lent && T[j]==T[j-i]; j++);

next[i]=j-i; p=i;
}
}

//for (int i=1; i<lent; i++) cout<<next[i]<<" ";
//cout<<endl;

/*===================求ex=====================*/

for (int i=0; S[i]==T[i]; i++) ex[0]++;

p=0;

for (int i=1; i<lens; i++)
{
int u=p+ex[p];

if (i+next[i-p]<u) ex[i]=next[i-p];
else
{
int j=u;

for ( ; j<lens && S[j]==T[j-i]; j++);

ex[i]=j-i; p=i;
}
}

int ans=0;

for (int i=0; i<lens; i++)
ans=max(ans,ex[i]);

cout<<ans;

return 0;
}




 
        
  评论这张
 
阅读(16)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018