字符串相关

emmmmmmmmmm

字符串Hash
https://www.byvoid.com/zhs/blog/string-hash-compare
注意小范围的话还是map好用,1e5内实测翻车

大名鼎鼎的KMP

参考资料:数据结构,邓俊辉

做点笔记,不然过两天又忘了...

KMP的快速来自于朴素算法的两个缺点:
1.匹配过程一旦失配则大幅滑动,而不是朴素算法的单一步进
2.失配后文本串T的i指针并不会蛮力回溯,充足的预案保证了位移后的失配点前P的前缀是一定匹配而不用再次比较
而2的前缀正确匹配的保证来自于1的滑动决策,也就是查询表next的构建,一旦j失配,只需j=next[j]继续匹配即可
用不是人话来说:
假设失配于指针i,j处,既T[i]!=P[j]则由当前的信息得知T[i-j,i)==P[0,j),
若P滑动位移为t,使得T[i]=P[t],
则对应1,T[i-j,i-t)不值得对齐并舍弃,又对应2,已知T[i-t,i)==P[0,t),既然一定匹配那i就不必回溯

关于next表
1.next[j]的定义是P[0,j)中最大自匹配的真前缀和真后缀的长度,通配符next[ 0]=-1
2.构建的过程是P与P的匹配过程
3.构建的方法使用的是递推,直接给出结论就是next[j+1]<=next[j]+1,当且仅当P[j]==P[next[j]]时等号成立,不等时就不断取next[...[j]]直到相等时+1,最坏情况就是next[j+1]=-1+1=0

不折不扣的模板

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int maxn = 1e5+100;
int next[maxn];
string P,T;
void buildNext(string &P){
    int len = P.length(), j = 0;
    memset(next,0,sizeof next); next[0]=-1;
    int t = next[0];
    while(j<len-1){
        if(t==-1||P[j]==P[t])
            next[++j]=++t;
        else
            t=next[t]; 
    } 
} 
int match(string &T,string &P){
    buildNext(P);
    int n = T.length(), i = 0;
    int m = P.length(), j = 0;
    while(j<m&&i<n){
        if(j==-1||T[i]==P[j]){
            i++;j++;
        } 
        else
            j=next[j];
    }
    return i-j;
}
int main(){
    cin>>T>>P;
    cout<<match(T,P)<<endl;
    return 0; 
}

待刷题:http://blog.csdn.net/lishaozhe1024/article/details/38454233
部分匹配


#include<iostream>
#include<stdio.h>


char W[10010],T[1000010];
int N;
int next[10010];


//match W again T, return the occurence
int kmp()
{
    //compute next of W
    int n=strlen(W+1);
    int m=strlen(T+1);
    next[1]=0;
    int i,j=0;
    for(i=2;i<=n;i++)
    {
        while(j>0 && W[j+1]!=W[i]) j=next[j];
        if(W[j+1]==W[i]) j++;
        next[i]=j;
    }
    //for(int i=1;i<=n;i++)
    //  printf("fail %d->%d\n",i,next[i]);
    int cnt = 0;
    j=0;
    for(i=1;i<=m;i++)
    {
        while(j>0 && W[j+1]!=T[i]) j=next[j];
        if(W[j+1]==T[i]) j++;
        if(j==n) cnt++;//,printf("found %d\n",i);
        
    }
    return cnt;
}
int main()
{
    scanf("%d",&N);
    while(N--){
        scanf("%s",W+1);
        scanf("%s",T+1);
        printf("%d\n",kmp());
    }
    return 0;
}

Manacher判断最长回文串

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e5+1e4+100;
char tstr[maxn],str[maxn<<1];
int len,tlen,rl[maxn<<1],pos,maxr,maxl;
int main(){
    while(scanf("%s",tstr+1)!=EOF){
        memset(str,0,sizeof str);memset(rl,0,sizeof rl);
        maxr=0; pos=0; maxl=0;
        tlen=strlen(tstr+1);
        len=2*tlen+1;
        for(int i = 1; i <= tlen; i++){
            str[2*i]=tstr[i];
            str[2*i+1]='#';
        }
        str[1]='#';str[len+1]='\0';
//        for(int i = 1; i <= len; i++) cout<<str[i];cout<<endl;
        for(int i = 1; i <= len; i++){
            if(i<=maxr) rl[i]=min(rl[2*pos-i],maxr-i);
            else rl[i]=0;
            while(i-rl[i]-1>=1&&i+rl[i]+1<=len&&str[i-rl[i]-1]==str[i+rl[i]+1]) rl[i]++;
            if(i+rl[i]>maxr){
                maxr=i+rl[i];
                pos=i;
            }
            maxl=max(maxl,rl[i]);
        }
        printf("%d\n",maxl);
    }
    return 0;
}

下次更新Sunday算法

不更了

Rabin-Karp
哈希的有用武器,感觉和进制的计算求和很像
char S="12345678" //1-based
设p为10,q为1e9+7;
hash(S)
=1×10^7+2×10^6+...+8×10^0
=Σ[i=1,len(S)]S(i)×p^[len-i] mod q //1+len-1-i
因为取模可能冲突,所以当hash值相同时再依次比较
同样,记S的子串Si为从第i个字符起长度为m的字符串
如i=4,m=3;
hash(Si)
=4×10^2+5×10^1+6×10^0
=Σ[j=i,i+m-1]S(j)×p^[i+m-1-j] mod q //和上式很像,i+m-1就是区间长加上相对偏移 j就是当前字符的绝对位置
hash(Si+1)
=5×10^2+6×10^1+7×10^0
=((4×10^2+5×10^1+6×10^0)-4×10^2)×10^1+7×10^0
=10^1×(4×10^2+5×10^1+6×10^0)+7×10^0-4×10^[2+1]
=[p×hash(Si)+S(i+m)-p^m×S(i)] mod q

标签: 算法, 学习

添加新评论