字符串整理

目录

字符串整理(Manachar,KMP,扩展KMP,ACAM,SA,SAM,最小表示法)

基础

  • 字符集(sum):一个字符集是一个建立了全序关系的集合，即任意属于(sum)的元素可以比较，字符集中的元素叫做字符
  • 字符串:一个字符串(S)将n个字符顺次排列组成，(n)为(S)的长度，计作(|S|)，此文使用的字符串均从1下标开始
  • 子串:字符串(S)的子串(S[i...j],i leq j),表示(S)串中从(i)到(j)这一段,也就是顺次排列(S[i],S[i+1],...,S[j])形成的字符串。
  • 子序列:字符串(S)的子序列是从(S)中将若干元素提取出来并不改变相对位置形成的序列,即(S[p_1],S[p_2],...,S[p_t]),(1 leq p_1 leq p_1 leq ... leq p_t leq |S|)。
  • 后缀:是指从某个位置(i)开始到整个串末尾结束的一个特殊子串。字符串(S)的从(i)开头的后缀表示为(Suffix(S,i)),也就是(Suffix(S,i)=S[i...|S|]),(suf(S,k)表示S后k个字符组成的后缀)。
  • 前缀:是指从串首开始到某个位置(i)结束的一个特殊子串。字符串(S)的从(i)结尾的前缀表示为(Preffix(S,i)),也就是(Preffix(S,i)=S[1...i]),(pre(S,k)表示S前k个字符组成的前缀)。
  • (Borde)r:(0 le r le |S|),(pre(S,r)=suf(S,r))，(pre(S,r))为s的(Border)
    (Border有)传递性，(Border)的(Border)还是原串的(Border)
  • 周期:(0 le p le |S|)，(S[i]=S[i+p],forall i in{1,2,...,|S|-p}),p为s的周期
    (pre(S,k))是(S)的(Border)(Leftrightarrow) (|S|-k)是(S)的周期
  • 自动机

KMP

  • (nwxt[i])表示(s[1..i])的最大的(Border)
  • 根据(Border)的传递性，我们记录s最大的(Border)后(mb(S))，s的所有(Border)为(mb(S),mb(mb(S)),...)
  • 求得时候运用border传递性与以求信息
  • 可以(O(N))进行单串的匹配
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000001;

char t[MAXN], s[MAXN];
int n, m;
int nxt[MAXN], k, ans, sh[MAXN];

int main() {
	
	scanf("%s", t + 1); 
    scanf("%s", s + 1);

    n = strlen(s + 1); m = strlen(t + 1);
    nxt[0] = -1; nxt[1] = 0;
    for (int i = 2; i <= n; i++) {
        k = nxt[i - 1];
        while(k != -1 && s[k + 1] != s[i]) {
            k = nxt[k];
        }
        nxt[i] = k + 1;
    }

    ans = 0; k = 0;
    for (int i = 1; i <= m; i++) {
        while(k != -1 && s[k + 1] != t[i]) {
            k = nxt[k];
        }
        k = k + 1;
        if(k == n) ans++, sh[ans] = i - n + 1;
    }

    for (int i = 1; i <= ans; i++) printf("%d
", sh[i]);
    for (int i = 1; i <= n; i++) printf("%d ", nxt[i]);
        
	return 0;
}

扩展KMP

  • 对于字符串(S)，(Z_i)表示(lcp(Suffix(S,i),S))
  • 在求解时充分利用已有信息（与manachar有相似之处）
  • 做i的时候，记录1..i-1中匹配到的lcp到达最右边的位置
#include <bits/stdc++.h>
const int N = 20000007;
int n, m, z[N], ext[N];
char s[N], t[N];
long long ans;
int min(int x, int y) {
	return x < y ? x : y;
}
inline void getz() {
	z[1] = n;
	ans ^= (1ll * 1 * (z[1] + 1));
	for (register int i = 2, l = 0, r = 0; i <= n; i++) {//r 维护当前匹配过的子串中达到的最右边的位置
		if(i <= r) z[i] = min(z[i - l + 1], r - i + 1);
		while(i + z[i] <= n && s[i + z[i]] == s[z[i] + 1]) ++z[i];
		if(i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
		ans ^= (1ll * i * (z[i] + 1));
	}
}
inline void exkmp() {
	for (register int i = 1, l = 0, r = 0; i <= m; i++) {
		if(i <= r) ext[i] = min(z[i - l + 1], r - i + 1);
		while(i + ext[i] <= m && t[i + ext[i]] == s[ext[i] + 1]) ++ext[i];
		if(i + ext[i] - 1 > r) l = i, r = i + ext[i] - 1;
		ans ^= (1ll * i * (ext[i] + 1));
	}
}
int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cin >> (t + 1);
	std::cin >> (s + 1);
	n = strlen(s + 1);
	m = strlen(t + 1);
	ans = 0;
	getz(); std::cout << ans << std::endl;
	ans = 0;
	exkmp(); std::cout << ans << std::endl;
	return 0;
}

Manachar

  • 用来寻找最长回文子串
  • 做的时候利用已有信息，记录当前曾到过的最右侧
#include <bits/stdc++.h>
using namespace std;
int const maxn = 11000000;
char s[maxn << 1];
int cnt;
int hw[maxn << 1], maxright, mid;
int ans;
inline void read() {
	char c = getchar();
	s[0] = '#'; s[cnt = 1] = '#';
	while(c > 'z' || c < 'a') c = getchar();
	while(c <= 'z' && c >= 'a') s[++cnt] = c, s[++cnt] = '#', c = getchar();
}
void manacher() {
	for (int i = 1; i <= cnt; i++) {
		if(i <= maxright) hw[i] = min(hw[(mid << 1) - i], maxright - i + 1);
		else hw[i] = 1;
		while(s[hw[i] + i] == s[i - hw[i]]) hw[i]++;
		if(hw[i] + i - 1 >= maxright) maxright = hw[i] + i - 1, mid = i;
		ans = max(ans, hw[i]);
	}
	
}
int main() {
	read();
	manacher();
	printf("%d", ans - 1);
	return 0;
}

Trie

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
int Trie[MAXN][30], tot = 1;
int en[MAXN];
void Insert(char* str) {
  int len =  strlen(str), p = 1;
  for (int i = 0; i < len; i++) {
    int ch = str[i] - 'a';
    if(Trie[p][ch] == 0) Trie[p][ch] = ++tot;
    p = Trie[p][ch];
  }
  en[p] = 1;
  return;
}
bool search(char* str) {
  int len = strlen(str), p = 1;
  for (int i = 0; i < len; i++) {
    int ch = str[i] - 'a';
    p = Trie[p][ch];
    if(p == 0) return 0;
  }
  return en[p];
}
int main() {
  return 0;
}

ACAM

  • AC自动机是一个形式上建立在trie上，实则是一个接受所有模式串的自动机
  • fail指针：fail(x)指向状态x的最长可识别后缀的状态位置
  • 求fail指针的时候可以沿当前节点往父亲节点跳，通过祖先节点来转移
  • 更方便的做法是用队列来逐层来求
  • 求出后应当建立出fail树，暴力跳fail指针效率较低
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define U(i,u) for(register int i=head[u];i;i=nxt[i])
#define rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define per(i,a,b) for(register int i=(a);i>=(b);--i)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> PII;
typedef vector<int> VI;
template<class T> inline void read(T &x){
	x=0;char c=getchar();int f=1;
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=x*10+c-'0';c=getchar();}x*=f;
}
template<class T> inline void cmin(T &x, T y){x=x<y?x:y;}
template<class T> inline void cmax(T &x, T y){x=x>y?x:y;}
const int N=5000010;
int n,match[N];
char s[N];
struct ACAM{
	int root,size,fail[N],to[N][27],head[N],nxt[N],v[N],cnt;
	inline void add(int x,int y){nxt[++cnt]=head[x];head[x]=cnt;v[cnt]=y;}
	inline int tn(int x,int y){
		return to[x][y]?to[x][y]:tn(fail[x],y);
	}
	inline void insert(char str[],int id){
		int len=strlen(str+1);
		int p=root;
		rep(i,1,len){
			int c=str[i]-'a'+1;
			if(!to[p][c])to[p][c]=++size;
			p=to[p][c];
		}
		match[id]=p;
	}
	inline void build(){
		size=root=1;rep(i,1,n){scanf("%s",s+1);insert(s,i);}
	}
	inline void getfail(){
		queue<int>q;rep(i,1,26)to[0][i]=1;q.push(1);
		while(q.size()){
			int u=q.front();q.pop();
			rep(i,1,26){
				if(to[u][i]){
					fail[to[u][i]]=tn(fail[u],i);q.push(to[u][i]);
				}
			}
		}
	}
	inline void buildfail(){rep(i,2,size){add(fail[i],i);}}
}acam;
int main(){
	return 0;
}

SA

#include<bits/stdc++.h>
const int N=1000010;
char s[N];
int n,m,num;
int sa[N],rk[N],bac[N],y[N],tmp[N];//sa[i]数组表示后缀排名为i的位置，rk[i]表示后缀[i..n]的排名
int height[N];//height[i]表示rk为i的后缀与rk为i-1的后缀的LCP
void getsa(){
    //rk[i]表示位置i的第一关键字(排名)
    //二元组(rk[i],rk[i+k])
    //初始化基数排序(单字符，其实是单元)
    for(int i=1;i<=n;i++)bac[rk[i]=s[i]]++;//bac[i]表示第一关键字小于i的个数
    for(int i=2;i<=m;i++)bac[i]+=bac[i-1];//故就先逐个统计，再求前缀和，相当于用桶计数
    for(int i=n;i>=1;i--)sa[bac[rk[i]]--]=i;//在第二关键字有序的情况下，对位置按照第一关键字的bac数组，逐个附排名 
    for(int k=1;k<=n;k<<=1){
        num=0;//排名的数量,初始化为单个字符的ASCLL码上限,m=ascll('z')=122
        //y[i]表示第二关键字排名为i的二元组的第一关键字位置(i)
        for(int i=n-k+1;i<=n;i++)y[++num]=i;//没有第二关键字的排名最靠前
        for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;//利用已有的sa_(k/2)数组，rk靠前的且有第一关键字的，将第一关键字位置sa_(k/2)[i]-k放入y
        //在上一轮中，rk_k数组已经求好了，倍增求解,
        //接下来利用基数排序，求出sa_k
        for(int i=1;i<=m;i++)bac[i]=0;
        for(int i=1;i<=n;i++)bac[rk[i]]++;//bac[i]表示第一关键字小于i的个数
        for(int i=2;i<=m;i++)bac[i]+=bac[i-1];//故就先逐个统计，再求前缀和，相当于用桶计数
        for(int i=n;i>=1;i--)sa[bac[rk[y[i]]]--]=y[i];//在第二关键字有序的情况下，对位置按照第一关键字的bac数组，逐个附排名 
        memcpy(tmp,rk,sizeof(tmp));//用tmp存一下rk_(k/2)，在求rk_k时仍会用到
        //其实就是利用sa_k和rk_(k/2)数组求rk_k
        rk[sa[1]]=1;num=1;
        for(int i=2;i<=n;i++){
            if(tmp[sa[i]]==tmp[sa[i-1]]&&tmp[sa[i]+k]==tmp[sa[i-1]+k])rk[sa[i]]=num;
            else rk[sa[i]]=++num;
        }
        if(num==n)break;//已经有了n种排名
        m=num;//m表示排名的数量（在桶排中为值域）
    }
}
void geth(){
    //rk[i]=rk1,sa[rk1-1]=x;
    //rk[i-1]=rk2,as[rk2-1]=y;
    //height[rk1]=lcp(s[i..],s[x...]);
    //height[rk2]=lcp[s[i-1..],s[y...]);
    //lcp(s[i..],s[x..])>=lcp(s[i-1...],s[y...])
    for(int i=1;i<=n;i++){
        int x=sa[rk[i]-1];
        int k=std::max(0,height[rk[i-1]]-1);
        while(s[i+k]==s[x+k])++k;
        height[rk[i]]=k;
    }
}
int main(){
    scanf("%s",s+1);n=strlen(s+1);m=122;
    getsa();for(int i=1;i<=n;i++)printf("%d ",sa[i]);
    printf("
");
    geth();for(int i=2;i<=n;i++)printf("%d ",height[i]);
    return 0;
}

SAM

  • SAM是一个最小的可以接受一个字符所有后缀的自动机
  • 构造的时候考虑用增量法，即每次放入一个字符
  • 构造完后，利用后缀连接link构造出link树（即parent树）
  • 即可得到所有的子串
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define U(i,u) for(register int i=head[u];i;i=nxt[i])
#define rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define per(i,a,b) for(register int i=(a);i>=(b);--i)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> PII;
typedef vector<int> VI;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void cmin(T &x, T y){x=x<y?x:y;}
template<class T> inline void cmax(T &x, T y){x=x>y?x:y;}
const int N=2000010;
char s[N];
int bac[N],a[N],cnt[N],n;
ll ans;
struct SAM{
	int size,last;
	int len[N<<1],link[N<<1];
	int to[N<<1][30];
	void extend(int c){
		int p,cur=++size;
		len[cur]=len[last]+1;
		for(p=last;p&&!to[p][c];p=link[p])to[p][c]=cur;//情况1
		if(!p)link[cur]=1;
		else{
			int q=to[p][c];
			//2-A类
			if(len[q]==len[p]+1)link[cur]=q;
			//2-B类
			else{
				int cl=++size;
				len[cl]=len[p]+1;
				memcpy(to[cl],to[q],sizeof(to[cl]));link[cl]=link[q];
				while(p&&to[p][c]==q){
					to[p][c]=cl;
					p=link[p];
				}
				link[cur]=link[q]=cl;
			}
		}
		last=cur;
		cnt[cur]=1;
	}
	void build(){
		scanf("%s",s+1);last=size=1;n=strlen(s+1);
		rep(i,1,n)extend(s[i]-'a');
	}
	void solve(){
		rep(i,1,size)bac[len[i]]++;
		rep(i,2,size)bac[i]+=bac[i-1];
		rep(i,1,size)a[bac[len[i]]--]=i;//对后缀长度排序
		per(i,size,1){
			int p=a[i];//排名为i的状态为p
			cnt[link[p]]+=cnt[p];
			if(cnt[p]>1)cmax(ans,1ll*len[p]*cnt[p]);
		}
		printf("%lld
",ans);
	}
}sam;
int main(){
	sam.build();
	sam.solve();
	return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/hangzz/p/13377950.html