字符串

字符串匹配

允许失配3次的字符串匹配

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;//自然溢出，这道题没被卡哇哈哈
const int N=100000+3,D=233;
int n,m,T,ans;
char a[N],b[N];
ULL p[N],f[N],g[N];
inline ULL ask(ULL*f,int l,int r){//[l,r]的哈希值 
	return f[r]-f[l-1]*p[r-l+1]; 
}
inline int lcp(int x,int y,int r){
	int l=1,mid,t=0;
	while(l<=r){//二分查找（这个东西可以让一个机房的人吵起来）
		mid=(l+r)>>1;
		if(ask(f,x,x+mid-1)==ask(g,y,y+mid-1)){//如果这一段是相等的 
			t=mid;//标记长度 
			l=mid+1;//l右移 
		}
		else r=mid-1;//不相等就左移 
	}
	return t;//返回长度 
}
inline bool check(int x){
	int r=x+m-1,y=1;//r：S0的尾；y:S的头
	for(int i=0;i<3;++i){//3次容错 
		int t=lcp(x,y,m-y+1);//相同的长度 
		// m-y+1
		x+=t+1;//不相等的那个要跳过 
		y+=t+1;
		if(y>m)return 1;//如果最终长度能>m,就匹配成功 
	}
	return ask(f,x,r)==ask(g,y,m);
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%s%s",a+1,b+1);
		n=strlen(a+1);
		m=strlen(b+1);
		if(n<m){//不解释
			printf("0\n");
			continue;
		}
		p[0]=1;
		for(int i=1;i<=n;++i)p[i]=p[i-1]*D;//预处理
		for(int i=1;i<=n;++i)f[i]=f[i-1]*D+a[i];//哈希值 
		for(int i=1;i<=m;++i)g[i]=g[i-1]*D+b[i];
		ans=0;
		for(int i=1;i+m-1<=n;++i)//枚举相同字符串的头 
			if(check(i))ans++;
		printf("%d\n",ans);
	}
	return 0;
}

前缀函数(pi)

#include<bits/stdc++.h>
using namespace std;
vector<int> pi(string s)
{
    int n=s.length();
    vector<int>ans(n,0);
    for(int i=1;i<n;i++)
    {
        int j=ans[i-1];
        while(j>0&&s[i]!=s[j])
            j=ans[j-1];
        if(s[i]==s[j])
            ans[i]=j+1;
        else
            ans[i]=0;
    }
    return ans;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        string s;
        cin>>s;
        vector<int> ans = pi(s);
        for(int i:ans)
            cout<<i<<" ";
        cout<<"\n";
    }


    return 0;
}

KMP

#include<bits/stdc++.h>
using namespace std;
vector<int> pi(string s)
{
    int n=s.length();
    vector<int>ans(n,0);
    for(int i=1;i<n;i++)
    {
        int j=ans[i-1];
        while(j>0&&s[i]!=s[j])
            j=ans[j-1];
        if(s[i]==s[j])
            j++;
        ans[i]=j;
    }
    return ans;
}
void kmp(string s,string t)
{
    int ls=s.length();
    int lt=t.length();
    string mid=t+"#"+s;
    vector<int>p=pi(mid);
    int num=0;
    vector<int>position;
    for(int i=lt+lt;i<ls+lt+1;i++)
    {
        if(p[i]==lt)
        {
            num++;
            position.push_back(i-lt-lt+1);
        }
    }
    cout<<num<<" ";
    for(int i:position)
        cout<<i<<" ";
    cout<<"\n";
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        string s;
        string t;
        cin>>s>>t;
        kmp(s,t);
    }

    return 0;
}