您的位置: 首页  >  文章  >  字符串基础算法

字符串基础算法

分类: 文章 • 2023-11-28 21:51:46

KMP

面向问题
在一个文本串中查找单个模式串

思路
利用nex数组移动模式串
nex[i]=j
表示b[0..j] = b[i-j..i]，取最大的y 
若不存在这样的y 则取nex[i]为-1
每次调用nex函数相当于推进模式串

代码如下

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

char a[10000],b[10000];
int next[10000];
int N,M,i,j;

int main()
{
	gets(a); N=strlen(a);   //  a为主串 
	gets(b); M=strlen(b);   // b为匹配串 
	next[0]=-1;
	j=-1;
	/*
	next[i]=j
	表示b[0..j]=b[i-j..i]取最大的j
	不存在这样的
	 */
	for (i=1; i<M; i++)
	{
		while (j!=-1 && b[i]!=b[j+1]) j=next[j];
		if (b[i]==b[j+1]) j++;
		next[i]=j; 
	}	// 类似于递推 
	for (i=0; i<M; i++) cout<<next[i]<<' '; cout<<endl;
	
	j=-1;
	// 不断跳 主串上的指针和字母串上的指针都在跳来跳去 next函数 实际上就是让模式串不断移动 
	for (i=0; i<N; i++)   
	{
		while (j!=-1 && a[i]!=b[j+1]) j=next[j];
		if (a[i]==b[j+1]) j++; //  
		if (j==M-1) cout<<i-M+1<<endl,j=next[j];     //当前位置可以匹配 
	}
	return 0;
}

 

exKMP

面向问题
给定主串S 和模式串T
求主串所有后缀和模式串的LCP

设辅助函数nex[i]表示T[i..m]与T的最长公共前缀长度。
利用nex函数进行快速计算（直接得到公式等）
其实还是利用nex函数推动模式串移动

设extend[1..k]已经算好，并且在以前的匹配过程中到达的最远位置是p。
最远位置严格的说就是i+extend[i]-1的最大值，不妨设这个取最大值的i是a

依据定义
S[a..p]=T[0..p-a+1]
可推得
S[k+1..p]=T[k-a+2..p-a+1]
这个时候我们就可以借助nex函数移动T了
设L=nex[k-a+2]
分两类计算 k+L<p  直接算，k+L>=p继续探测
具体细节参照ppt
字符串基础算法

字符串基础算法

字符串基础算法

完整代码

const int maxn=100010;   //字符串长度最大值
int nex[maxn],ex[maxn]; //ex数组即为extend数组
//预处理计算nex数组
void GETnex(char *str)
{
    int i=0,j,po,len=strlen(str);
    nex[0]=len;//初始化nex[0]
    while(str[i]==str[i+1]&&i+1<len)//计算nex[1]
    i++;
    nex[1]=i;
    po=1;//初始化po的位置
    for(i=2;i<len;i++)
    {
        if(nex[i-po]+i<nex[po]+po)//第一种情况，可以直接得到nex[i]的值
        nex[i]=nex[i-po];
        else//第二种情况，要继续匹配才能得到nex[i]的值
        {
            j=nex[po]+po-i;
            if(j<0)j=0;//如果i>po+nex[po],则要从头开始匹配
            while(i+j<len&&str[j]==str[j+i])//计算nex[i]
            j++;
            nex[i]=j;
            po=i;//更新po的位置
        }
    }
}
//计算extend数组
void EXKMP(char *s1,char *s2)
{
    int i=0,j,po,len=strlen(s1),l2=strlen(s2);
    GETnex(s2);//计算子串的nex数组
    while(s1[i]==s2[i]&&i<l2&&i<len)//计算ex[0]
    i++;
    ex[0]=i;
    po=0;//初始化po的位置
    for(i=1;i<len;i++)
    {
        if(nex[i-po]+i<ex[po]+po)//第一种情况，直接可以得到ex[i]的值
        ex[i]=nex[i-po];
        else//第二种情况，要继续匹配才能得到ex[i]的值
        {
            j=ex[po]+po-i;
            if(j<0)j=0;//如果i>ex[po]+po则要从头开始匹配
            while(i+j<len&&j<l2&&s1[j+i]==s2[j])//计算ex[i]
            j++;
            ex[i]=j;
            po=i;//更新po的位置
        }
    }
}


/*
我们会发现算extend函数的代码和算nex函数是一模一样！
这是因为nex实际上以T为母串、T为子串的一个特殊“扩展的KMP” 
*/

马拉车

Ma[i]表示i能向两边推（包括i）的最大距离，如果能求出Ma，则答案就是max(Ma)-1了（以i为中点的最长回文为2*Ma[i]-1，但这是加过字符后的答案，把加进去的字符干掉，最长回文就是Ma[i]-1）。

我们假设Ma[1~i-1]已经求好了，现在要求Ma[i]： 
假设当前能达到的最右边为R，左边界为对应的中点为pos，j是i的对称点。 

1、当i＜R时 
     情况1：由于L~R是回文，所以Ma[i]=Ma[j]（i的最长回文和j的最长回文相同）。 

字符串基础算法
     情况2：这种情况是另一种：j的最长回文跳出L了。那么i的最长回文就不一定是j的最长回文了，但蓝色的肯定还是满足的。
     综上所述，Ma[i]=min(Ma[2*pos-i],R-i)。 

字符串基础算法

2、当i>=R时
     由于后面是未知的，于是只能暴力处理了，在暴力的时候记得更新pos。

来自kuangbin的模板

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

const int MAXN=110010;
char Ma[MAXN*2];
int Mp[MAXN*2];
char s[MAXN];

void Manacher(char s[],int len)
{
	int l=0; Ma[l++]='$';
	Ma[l++]='#';
	for(int i=0;i<len;i++) {
		Ma[l++]=s[i];
		Ma[l++]='#';
	}
	Ma[l]=0;
	int mx=0,id=0;
	for(int i=0;i<l;i++)  {
		Mp[i]=mx>i ? min(Mp[2*id-i],mx-i):1;
		while(Ma[i+Mp[i]]==Ma[i-Mp[i]]) Mp[i]++; 
		if(i+Mp[i]>mx) {
			mx=i+Mp[i]; id=i;
		}
	}
}
/*
* abaaba
* i:	0 1 2 3 4 5 6 7 8 9 10 11 12 13
* Ma[i]: $ # a # b # a # a $ b  #  a #
* Mp[i]: 1 1 2 1 4 1 2 7 2 1 4  1  2 1
*/
int main()
{
	while(scanf("%s",s)==1)
	{
		int len=strlen(s); 
		Manacher(s,len); 
		int ans=0;	
		for (int i=0;i<2*len+2;i++) ans=max(ans,Mp[i]-1);
		printf("%d\n",ans);
	}
	return 0;
}

 

相关推荐