当前位置：网站首页>专题讲座8 字符串(一) 学习心得

专题讲座8 字符串(一) 学习心得

2022-08-11 08:30:00 【繁水682】

板子与框架

字符串基础

这场学了不少东西，有些简单的知识比较好掌握，成就感满满

板子与框架

字符串基础

字符串：由若干个字符按顺序拼接而成的序列
S[1…n]：长度为 n 的字符串 S
S[i]：字符串 S 的第 i 个位置的字符
S[L…R]：字符串 S 的下标区间为 [L,R] 的一段连续子串，特殊的，空串和 S 本身也为 S 的子串
字符集Σ：包含 S 中出现的所有字符的集合（通常为大/小写字母） Prefix[i]=S[1…i]：字符串 S 的第 i 个前缀
Suffix[i]=S[n-i+1…n]：字符串 S 的第 i 个后缀
LCP(S,T)：S 与 T 的最长公共前缀 Longest Common Prefix
LCS(S,T)：S 与 T 的最长公共后缀 Longest Common Suffix
字符串的大小比较一般按照字典序，即从第一位至最后一位按位比较，若长度不同则在较短的字符串后补上足够的空字符（空字符被认为比任何字符都要小）
比如 “abc”>“ab”，“abc”<“ac”
若存在小于等于 n 的正整数 k 满足 ∀𝑖∈[1,𝑛−𝑘]∩𝑍，有 S[i]=S[i+k]，则称 k 为 S 的一个周期比如 3 是 “abcabcab” 的一个周期，2是 “aaa” 的一个周期，1 是其最小周期
border——前后缀相等的那段字符串

最小表示法

char s[N];
int n;
int getmin(){
    int i=0,j=1,k=0,t;
    n=strlen(s);
    while(i<n&&j<n&&k<n){
        t=s[(i+k)%n]-s[(j+k)%n];
        if(!t) k++;
        else{
            if(t>0) i+=k+1;  else j+=k+1;
            if(i==j) j++;
            k=0;
        }
    }
    return min(i,j);
}

哈希

#define ull unsigned long long
const int x=131;
ull h[N],p[N]; 
p[0]=1;
rep(i,1,n){
	h[i]=h[i-1]*x+s[i];//按权展开相加 
	p[i]=p[i-1]*x;//预处理 
}
ull get(int l,int r){
    return h[r]-h[l-1]*p[r-l+1];//前缀和的感觉 
}

KMP

char ss[N],s[N];
int nxt[N];
int len1,len2;
void get_next(){
	int i=0,j=-1;nxt[0]=-1;
	while (i<len2){
		if (j==-1||s[i]==s[j])
			i++,j++,nxt[i]=j;
		else
			j=nxt[j];
	}
}
void bijiao(){
	int i=0,j=0;
	while (i<len1){
		if (j==-1||ss[i]==s[j])
			i++,j++;	
		else
			j=nxt[j];
		if (j>=len2) cout<<i-j+1<<endl;
	}
}

失配树

vector <int> ve[N];
char s[N];
int nxt[N];
int f[N][20],dep[N];
int len;
int lca(int x,int y){
	if (dep[x]<dep[y]) swap(x,y);
	nep(i,19,0) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	if (x==y) return x;
	nep(i,19,0) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}
void dfs(int u,int fa){
	dep[u]=dep[fa]+1;f[u][0]=fa;
	rep(i,1,19) f[u][i]=f[f[u][i-1]][i-1];
	for (int i=0;i<ve[u].size();i++){
		int v=ve[u][i];
		if (v==fa) continue;
		dfs(v,u);
	}
}
void get_next(){
	int i=0,j=0;ve[0].pb(1);
	for (i=2;i<=len;i++){
		while (j>0&&s[j+1]!=s[i]) j=nxt[j];
		if (s[j+1]==s[i]) j++;
		nxt[i]=j;
		ve[j].pb(i);
	}
}
void work(){
	cin>>s+1;
	len=strlen(s+1);
	get_next();
	dfs(0,0);
	int q;cin>>q;
	rep(i,1,q){
		int x,y;cin>>x>>y;
		int l=lca(x,y);
		if (l==x||l==y){
			cout<<nxt[l]<<endl;
		} 
		else{
			cout<<l<<endl;
		}
	}
}

扩展KMP

暂无

Manacher

char s[N],str[N];
int p[N];
int len;
void manacher(){
	len=strlen(s+1);
	str[0]='$';str[1]='#';//初始化新字符串 
    for(int i=1;i<=len;i++){
        str[i*2]=s[i];
        str[i*2+1]='#';
    }
    len=len*2+2;
    str[len]='#';
    
    int id=0,mx=0; 
    for(int i=1;i<len;i++){
        if(mx>i)
            p[i]=min(p[2*id-i],mx-i);//记忆化 
        else
        	p[i]=1;
        while(str[i-p[i]]==str[i+p[i]]) p[i]++;
        if(p[i]+i>mx){//如果发现更靠右的盒子 
            mx=p[i]+i;
			id=i;
        }
    }
}

字典树

int cnt=0;
int pre[N];
char s[N];
int tr[N][70];
int getnum(char c){
    if('A'<=c&&c<='Z')
        return c-'A';
    else if('a'<=c&&c<='z')
        return c-'a'+26;
    else
        return c-'0'+52;
}
void insert(){
	int p=0,len=strlen(s);
	for (int i=0;i<len;i++){
		int c=getnum(s[i]);
		if (!tr[p][c]) tr[p][c]=++cnt;
		p=tr[p][c];
		pre[p]++;
	}
}
int find(){
	int p=0,len=strlen(s);
	for (int i=0;i<len;i++){
		int c=getnum(s[i]);
		if (!tr[p][c]) return 0;
		p=tr[p][c];
	}
	return pre[p];
}
void work(){
	rep(i,0,cnt){
		rep(j,0,70){
			tr[i][j]=0;
		}
	}
	rep(i,0,cnt){
		pre[i]=0;
	}
	cnt=0;
	int n,q;cin>>n>>q;
	rep(i,1,n){
		cin>>s;
		insert();
	}
	rep(i,1,q){
		cin>>s;
		cout<<find()<<endl;
	}
}