首页 > 其他分享 >字符串

字符串

时间：2024-07-04 12:08:41浏览次数：23  
标签：fa 后缀 tr len fail 字符串 节点

AC自动机

用于多个模式串（模式串在文本串里面出现），和文本串匹配

对模式串建立trie, 每个点上维护一个fail, 每个节点其实代表一个前缀。若干个模式串形成了若干个前缀字符串集合S。fail[i]表示S中的所有字符串中，能和i这个字符串的后缀完全匹配的最长字符串。 (当然这个字符串不能是i本身), 如果没有，那么是根节点，表示为空

那么fail, fail[fail],fail[fail[fail]]].... 就是i的所有后缀集合（每个后缀都要作为前缀在trie里面出现过）。每次跳fail都会向上一层

那么对于trie[p][c] = u;

int nw = fail[p]; while (!tr[p][c] && p) p = fail[p];

fail[u] = tr[p][c];

我们进行bfs, 那么p的fail已经处理完了，现在要处理u的fail,那么就从长往短不断跳p的后缀，直到遇到一个tr[p][c]不是空的为止

但是实际的写法是：

void build() {
  for (int i = 0; i < 26; i++)
    if (tr[0][i]) q.push(tr[0][i]);
  while (q.size()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
      if (tr[u][i])
        fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]);
      else
        tr[u][i] = tr[fail[u]][i];
    }
  }

q里面是已经处理好fail的点， 扩展u的子节点。我们没有while循环。因为tr[u][i]表示的就是不断跳fail，直到有人的[i]不是空的那个节点。对于u的子节点,可以直接fail[tr[u][i]] = tr[fail[u]][i]; // tr[fail[u]][i]里面存储的就是一直跳fail以后到达的点。怎么实现的呢？

如果tr[u][i]是空的，就变成tr[fail[u]][i]. tr[fail[u]][i]是不断跳以后的位置，所以tr[u][i]也是

查询:(只适用于每个点访问一次以后可以直接打标记，之后不会再访问。能保证O(n), 否则每次一直跳fail是n^2,需要优化）， 这种查询方式只适用于简单版1,2

int query(char *t) {
  int u = 0, res = 0;
  for (int i = 1; t[i]; i++) {
    u = tr[u][t[i] - 'a'];  // 转移
    for (int j = u; j && e[j] != -1; j = fail[j]) {
      res += e[j], e[j] = -1;
    }
  }
  return res;
}

同时这样求出来的也是最靠前的位置，只需要用vector,第一次访问的时候记录答案。然后把这次访问的点都标记为vis,之后不再访问

最后一次出现，所有串都反过来。求出的是结尾的位置，需要+串的长度才行

如果是求出现在其中的串的个数，访问一个点就可以直接vis=1了，所以总复杂度是O(n)

如果是求每个点出现次数，或者出现总次数，就要优化了

几个模式串在文本串第k次出现的位置

原串 # 询问串1询问串2... (#是分隔符，用来防止出现那种原来的串本来没有，但是由于询问串直接拼接导致错误，加一个分割就没事）

然后后缀排序，比如询问串是bac,那么所有以bac开头的后缀是一个连续的区间。rk[询问串i]就是这个询问的排名，用height数组求LCP，二分一下所有以询问串i开头的后缀的范围。然后求一下区间k小值（大小按照第一次出现的位置作为关键字）

https://www.luogu.com.cn/problem/P3796
这道题就没法用vis标记，每次最多跳max(模式串）,一共t次，所以是70*t的复杂度

优化之后： 每个点向自己的fail链接一条有向边，这样会构成一个以0为root的树。从下往上topsort,或者维护子树信息，合并上来

可以做到O(tot), tot是模式串总点数

总复杂度： O(tot*w) + O(n), n是文本串长度（在trie树上走,需要O(n), w是字符集大小）

https://www.luogu.com.cn/problem/CF547E

差分，变成前缀里面出现多少次。询问离线。考虑1~i的串对询问串k的贡献。建立出来所有串的AC自动机。每个i串，在AC自动机上面遍历到len个节点，每个节点不断跳fail,所有fail++,最后查询k所在节点的权值。树状数组维护

fail树可以结合各种东西，一些不断跳fail的操作，都可以转化成一条链上操作。

https://www.luogu.com.cn/problem/P2292

AC自动机fail的实质就是找到当前点的所有后缀，枚举所有前缀里面是某个串后缀的所有串。
所以就可以有转移,枚举所有后缀（这些后缀都是合法单词），然后从fi-后缀长度转移
复杂度mts, 考虑优化，发现不太能topsort
发现s很小，可以预处理出来，得到每个点上面所有合法的单词长度构成一个集合
然后20个f，也构成一个集合，&一下，如果是1，说明这个是1
如果s大一点，也可以bitset

https://qoj.ac/contest/1037/problem/5034

具体题解题目那有。以及https://www.cnblogs.com/Harry27182/p/17971173

不能经过某个路径i,假设i结尾的那个节点是k,那么就是所有跳fail能调到k的都不能选。也就是fail树上每个k的子树的所有点。标记这些点不需要建树，可以直接求fail的时候vis[x] |= vis[fail[x]],要按照相邻的顺序

考虑把每个点接受到一个字符到达的点和这个点连边，但是这个是n^2的

发现如果tr[x][i]是空的，就相当于一直跳fail, 然后和fail的那个点连到同一个节点。这些边中，只有一个能松弛那个终点，所以这个边可以公用，第一次松弛以后就直接删除。用可持久化线段树

对于字符集比较大的时候，那些空节点在字典图上的连边没法一一找。 可以用主席树，以字符集为下标。每个点直接继承fail[x]的所有信息，然后对于那些非空节点，直接修改即可

https://www.luogu.com.cn/problem/P2414

不能在别的里面出现，就是fail子树打标记。这道题可以离线dfs,动态用树状数组维护插入

...在这个串出现，就是当前点到根的路径

https://www.luogu.com.cn/problem/P7456

维护最长可以匹配字符串。维护后缀最小值

对于一类维护单调栈，然后查询某个元素对应栈里面的那个位置（比如离他最近的栈的元素eg(本题），或者小于他的点的个数(eg.丹钓栈)）可以用并查集

while (top && f[i] <= f[stk[top]])
	fa[stk[top]] = i; top--;

https://www.luogu.com.cn/problem/P3311

数位dp, dfs写法无法滚动数组

后面是否卡上界以及是否前导0可以不用把数组开出来。数组里面只记忆化没有前导0，没有卡上界的。

但是dfs的时候仍然正常传入lim和zer. 如果dfs发现!lim && !zer,才去看是否被记忆化过。否则如果lim或者zer,直接搜到底（复杂度是对的，因为本身卡上界以及前导0的情况就那n种，且有前导0，lim的情况本身就只会被用到1次，不需要记忆化）//!!!!!!一定要注意最后必须没有lim和zer才能更新 记忆化数组

ll dfs(int p, int x, bool lim, bool zer) {
	if (!p) return 1;
	ll v = f[p][x]; //后面的两个维度可以不存。  f[x][y]表示lim = 0 并且zer = 0的时候的情况
	//对于lim = 1 或者 zer = 1 的情况都很少直接爆搜 
	if (~v && !lim && !zer) return v;
	v = 0;
	for (int i = 0; i < 10; i++) {
		if (lim && i > a[p]) break;
		int to = (!zer || i) ? tr[x][i] : x;
		if (vis[to]) continue;
		v = (v + dfs(p - 1, to, lim && (i == a[p]), zer && !i)) % mod;
 	} if (!lim && !zer) f[p][x] = v; //!!!!!!一定要注意最后必须没有lim和zer才能更新 
	return v;
}

https://www.luogu.com.cn/problem/P5840

完整虚树差分技巧（每个点到根的路径并上+1（重复的时候只加一次）），每个点++,在相邻两个的lca--, (1和n之间的lca不用)，如果不想要到根的，就在fa[lca(1,n)]上--

https://www.luogu.com.cn/problem/P3715

https://blog.csdn.net/woshi250hua/article/details/7599472

没法两个都建AC自动机（没法转移），那就枚举一整个下一个可用单词，然后把禁忌词汇建立AC自动机dp

可以矩阵优化dp, 如果基础词汇长度只有1,2，那就存[f[i-2,0~tot], f[i-1,0~tot]]一共两百个数，当做一个向量，进行转移

!!!!!!!!!!!!!!构造初始矩阵，或者初始方程的时候，都写 成+=, 不要写成=， 因为可能一个位置不只是被加一次

https://www.luogu.com.cn/problem/P6125

题解 https://blog.sengxian.com/solutions/bzoj-1444

//如果把f[i]定义成经过过i的概率，转移的方程是错的，

//因为如果先经过一次，这个概率就已经算完了，但是可能会出现先到达这个点一次，又到达一次，然后把第二次到达的概率也加上了

//所以要么就枚举每个点i,每次设fi表示从i出发能让i获胜的概率

//要么就用fi表示经过i的期望次数 。 因为终止节点经过一次就结束了，所以它的期望就是它的概率，因为期望等于经过i次的概率*i

//叶子节点（也就是答案节点）只会经过1次，所以就是概率，而其他节点就转换成期望

//!!!!!!!!!!由于我们设置的是期望，所以当没有人会赢的时候，0的期望次数是正无穷，
//也就是f[0] = f[0] + 1 ， 对应的就是无解的情况,所以直接return，这样所有人的概率都是0

一定要注意概率为0的特殊情况

后缀数组

https://oi-wiki.org/string/sa/#结合并查集

https://www.cnblogs.com/alex-wei/p/Basic_String_Theory.html

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
	ll x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	} return x * f;
}//oldrk不用2倍也行，但最好是(虽然32行有sa[i]+w, 但是执行到这个一定满足了oldrk[sa[i]]==oldrk[sa[i-1]],这个时候一定能保证sa+w-1<=n 
const int N = 1e6 + 10;
int sa[N], rk[N], n, id[N], oldrk[N*2], cnt[N], m, h[N]; char s[N]; //cnt的是值域 
int main() { //这里的rk，如果两个权值相同，rk也相同，但是最后的每个后缀一定rk互不相同。 
	scanf("%s", s + 1); n = strlen(s + 1); m = 150; oldrk[n+1] = 0; 
	//!!!一定要保证ork[n+1]=0，因为可能会用到ork[n+1]和ork[i]的比较，必须要让ork[n+1]是独一无二的 
	for (int i = 1; i <= n; i++) cnt[rk[i] = s[i]]++; //!!!!!!!!!一定要保证rk[i]不能是0,因为为了放置rk[1] = rk[0]导致rk从0开始标 
	for (int i = 1; i <= m; i++) cnt[i] += cnt[i-1];
	for (int i = n; i >= 1; i--) sa[cnt[rk[i]]--] = i; //!!!!!!这里不代表cnt已经清空 
	for (int w = 1, p = 0; ; w <<= 1, m = p, p = 0) { //不要写<n, 因为如果n=1,rk[1] = 97不是1, 直接不写就行 
		for (int i = n; i >= n - w + 1; i--) id[++p] = i; //先按照第二个维度排序，后w个点的第二维是空的，所以在前面 
		for (int i = 1; i <= n; i++) if (sa[i] > w) id[++p] = sa[i] - w;//对1~n-w的第二个维度排序 
		for (int i = 1; i <= m; i++) cnt[i] = 0; p = 0; //!!!!!!!!!注意p = 0,因为下面需要用p标号 
		for (int i = 1; i <= n; i++) oldrk[i] = rk[i];
		for (int i = 1; i <= n; i++) cnt[rk[i]]++; //这里不用id[i],因为反正只是记一下数 
		for (int i = 1; i <= m; i++) cnt[i] += cnt[i-1];
		for (int i = n; i >= 1; i--) sa[cnt[rk[id[i]]]--] = id[i]; 
		//!!!!!!!!!!!!!!!!!这里一定是rk[id[i]] 不是rk[i],因为需要用id[i]按照第二维排序的结果对第一唯一排序 
		for (int i = 1; i <= n; i++) rk[sa[i]] = (oldrk[sa[i]] == oldrk[sa[i-1]] && oldrk[sa[i]+w] == oldrk[sa[i-1]+w]) ? p : ++p;
		if (p == n) break;//说明没有大小关系相同的两个元素 
	}
	for (int i = 1, p = 0; i <= n; i++) { //用这种写法，前提是0,n+1=空的   以及sa[0] = 0 
	//p表示已经确定了长度为p是合法, 开始要先p-- 
		if (p) p--; int j = sa[rk[i]-1]; 
		while(s[i+p] == s[j+p]) p++;
		h[rk[i]] = p;
	}
	return 0;
}

oldrk只需要开到n+1即可，但是记得oldrk[n+1] = 0

因为如果oldrk[sa[i]] == oldrk[sa[i-1]]成立才会继续执行，如果执行这个，说明sa[i]和sa[i-1]都是长度为w的，所以sa[i]+w <= n + 1，所以只需要oldrk <= n

后缀数组的应用

寻找最小的循环移动位置

在字符串中找子串：同一个前缀后缀排序以后连续， 二分即可，详情见： AC自动机后缀数组写法

从字符串首尾取字符最小化字典序: 这一次选择头还是尾，就看正串和反串那个大，这个直接拼到一起后缀数组即可

height数组

h[i]表示排序后第i个和第i-1的最长公共前缀

有性质： h[rk[i]] >= h[rk[i-1]]-1

证明: 由于h[rk[i-1]] 是 sa[rk[i-1]]和 sa[rk[i-1]-1]两个字符串的lcp, 也就是i-1和 sa[rk[i-1]-1]

如果h[rk[i-1]] <= 1,结论一定成立，否则i-1和sa[rk[i-1]-1] 可以分别表示成aAD和aAB 其中a是一个字符，A是非空字符串， B < D， 那么i就是AD。

sa[rk[i]-1]一定< AD, 因为存在AB的后缀，且sa[rk[i]-1]是最靠近AD的

所以AB <= sa[rk[i]-1] < AD 所以sa[rk[i]-1]和i的lcp >= las-1

	for (int i = 1, p = 0; i <= n; i++) { //用这种写法，前提是0,n+1=空的   以及sa[0] = 0 
	//p表示已经确定了长度为p是合法, 开始要先p-- 
		if (p) p--; int j = sa[rk[i]-1]; 
		while(s[i+p] == s[j+p]) p++;
		h[rk[i]] = p;
	}

应用:

两子串最长公共前缀： ！！！是rk[i]+1 ~ rk[j]

比较一个字符串的两个子串的大小关系: [a,b]和[c,d]的大小，分类：lcp(a,c)>=min(len1,len2),长度长的大（相等就一样大）。否则就是rk[a]和rk[c]直接比较（因为在前min(len1,len2)位就得到胜负了)

不同子串的数目

按照rk的顺序加入， 每次重复的部分就是当前i和之前加入的字符串集合里面lcp最大的，正好就是h[i]（就是和最相邻的那个之间的lcp)

https://www.cnblogs.com/alex-wei/p/Basic_String_Theory.html

出现至少 k 次的子串的最大长度

出现至少 k 次意味着后缀排序后有至少连续 k 个后缀以这个子串作为公共前缀。

是否有某字符串在文本串中至少不重叠地出现了两次 :

可以二分目标串的长度 |s|，将 h 数组划分成若干个连续 LCP 大于等于 |s| 的段，利用 RMQ 对每个段求其中出现的数中最大和最小的下标，若这两个下标的距离满足条件，则一定有长度为 |s| 的字符串不重叠地出现了两次。

注意：排名连续不一定实际连续

结合单调栈 : https://www.cnblogs.com/alex-wei/p/Basic_String_Theory.html

//	stk[++top] = 1; //方法1 
//	for (int i = 1; i <= n; i++) { //!!!!!!!!!是stk[top-1]~stk[top]-1为合法，因为i~j对应的h区间是i+1~j 
//		//!!!!!!!!是按照sa的顺序从小往大，不能按照原顺序，因为就算转个顺序也成立 
//		while (top > 1 && h[stk[top]] >= h[i]) {
//			f -= 1ll * h[stk[top]] * (stk[top] - stk[top-1]); top--;
//		} f += 1ll * h[i] * (i - stk[top]); stk[++top] = i; ans -= 2 * f; 
//		//!!!!!这个-=f要放在后面 ,因为i弄完以后是左端点在1~i-1 
//	} cout << ans;
	stk[++top] = 1; L[1] = R[1] = 1; 
	for (int i = 2; i <= n; i++) {
		while (top && h[stk[top]] >= h[i]) R[stk[top]] = i, top--;
		L[i] = stk[top]; stk[++top] = i;
	} while (top) R[stk[top]] = n + 1, top--; //!!!!!!!一定要记得这一步 
	for (int i = 1; i <= n; i++) ans -= 2ll * (i - L[i]) * (R[i] - i) * h[i]; //从前半和后半分别选择一个
	cout << ans;

P2463 3.4.4 多个串的最长公共子串

双指针：选择排序后的l~r的区间，用cnt数组（int类型,记录次数)记录这些后缀是否在每个串里面出现，只有都出现才合法。

https://www.luogu.com.cn/problem/P1117

找到每个点作为开头，结尾，形如AA的个数: 用f/g数组表示

枚举A的长度len, 每间隔len个划分一个关键点，每个AA经过两个关键点，枚举每一组p, q两个相邻关键点，找到以p,q为开头的后缀的时候的最长公共前缀cr，以及p,q为结尾的是哦胡的最长公共后缀cl。如果cl + cr >= len + 1,那么合法，会贡献出cl+cr-len种不同的覆盖方案。然后就是差分，区间加得到f,g

后缀自动机

推荐文献：

洛谷网校（算法过程，算法流程的时间复杂度，算法性质，算
法应用）

oiwiki 和
https://www.cnblogs.com/alex-wei/p/Common_String_Theory_Theory_automaton_related.html

可以看看性质，应用，例题，

关于节点数，转移数，额外信息的证明可以看oiwiki(也可以参考alex-wei), 但是操作数的证明，看洛谷就行

一些概念：

后缀自动机是用来接受一个字符串的所有字串的结构（后缀的前缀）

时间复杂度O(n+wn) w是字符集大小（如果比较大的时候，可以用map, 或者可持久化线段树，做到nlogw)

空间O(2*n) 或者 2nlogn之类的

!!!一定要二倍空间： 因为每次可能会分裂出来一个节点

常见应用特征???：

每个节点（状态）是一类endpos相同的字串（这些字串满足是某一段前缀的后缀），两个节点的endpos要么包含关系，要么不相交（cmd的博客)

转移： 构成一个DAG, 就是每个状态接受一个字符以后转移到的状态。

len: 每个状态最长的字串的长度

终点节点： 每次刚调用expand的时候新建的那些节点（分别代表原串的n个前缀）

后缀链接(fa) : 每个终点节点出发，跳fa, 所有节点代表的字串的集合，就是这个终点节点所在前缀的所有后缀。

流程

（参考着洛谷网校的讲解或者ppt）

1是根节点， 0是空节点 (fa[1] = 0, 其他的节点fa[i] = 1或者别的正数）

for1~n, 每次expand一个字符c，上一次的终点字符称为las.

  1. 新建一个新的终止节点cur(最后记得把las = cur), len[cur] = len[las] + 1

  2. 从las不断跳fa(相当于遍历i-1前缀的所有后缀）到达节点p(p包含las)， 如果发现没有tr[p][c]的转移，那就把tr[p][c] = cur

  3. 否则到达节点np, int q = tr[np][c]：

    分类:

    l. 如果p是0， fa[cur] = 1, return

    1. 如果len[p] + 1 == len[q], 说明q正好就是np+了一个c构成的， 这个时候直接fa[cur] = q; return

    2. 否则就新建建立一个节点nq(这个节点不算终点节点）， 把tr[q]的所有转移边复制到tr[nq], fa[nq] = fa[q]; 饭后一直跳q的fa, 如果tr[q][c] == q, tr[q][c] = nq; (如果遇到一个不是的时候，就可以直接break了， 因为根据定义，每个状态存储的字串， 都是连续的，所以连接到他的节点也一定是连续的）

时间复杂度

首先我们定义最后一次添加完以后，的las节点不断跳fa所能到达的节点集合是终止节点（！！！不是终点节点），终止节点对应的字符串都是原字符串的后缀

  1. 节点个数是2n-1: 因为每次最多添加2个节点

  2. 转移边的个数是3n-3, 首先我们定义连续转移是一条转移边p->q, 满足len[p] + 1 == len[q](每个点都会有一个这样的父亲转移到他，因为每次新建一个cur,las->cur一定就是这样的边，如果是nq类节点，也可以用类似的方法分类讨论证明）, 连续转移边一定构成一个树所以，连续转移的数量是2n-2的

    对于不连续的转移： p通过c到达q, 那么找到一条根到p的路径构成的字符串u, 一条q到终止节点的字符串v, 那么这个字符串是Sp,q = u+c+v. 由于后缀自动机上面每个节点，每条路径代表的字符串都是独一无二的，所以对于两组p,q, 他们的Spq是不相同的， 原串最多有n个不同的后缀，所以Spq最多n种 总共3n-3

  3. 关于操作流程里面第一步：跳p的fa,如果没有ch的转移，就连接到当前节点。 我们比较加入这个节点前las的父亲len1，和加入以后,las的父亲的len2（也就是cur的父亲）。如果只跳一次，就是len2 = len1 + 1（只跳一次）
    之后，每当多跳一次，len2都会在这个基础上至少-1，所以总增加量是O(n), 每O(1)的时间， 就会让这个值-1，所以是O(n)

  4. 关于，流程操作2.（3） ： las不断跳fa,会构成一条链1， cur不断跳fa,也会构成一条链2。las的路径上的每个点都会连接到链2上一段连续的区间，并且越考上的链1上的点，连接到2的点越考上： 因为链1对应的是上一个所有后缀，链2对应的是加一个字符以后的所有后缀，所以需要用上一个+c,也就是转移边链接过来（所以都有边，且根据len的大小关系可以得到顺序）

    类比上一个证明，我们以las的fa的fa的len作为是能函数.由于一个点的len等于所有能转移到他的点的len的最大值+1（？？？）这种情况下，就是最下面的那个点+1.

    如果只有tr[p][ch] != 0, 那么cur的fa的fa最好也只能被fa[fa[p]]链接，len是fa[fa[p]].len + 1

    而每当向上多跳一步，len[fa[fa[cur]]]都会至少比原来的基础上少1

  5. memcpy的时候时间复杂度是n*26， 如果用可持久化线段树或者map，O(nlogn)复杂度(因为一共3n条转移边）

性质

  1. 每个节点的终点集合at（也就是在哪些位置出现过），等于其 子树 内所有终点节点对应的终点的集合。 但是注意，终点节点不一定都是叶子节点，比如aa(当且仅当一个字符串存在一个前缀是另一个前缀的后缀）

  2. 所有fa的关系构成一棵树（注意，转移边不算).在每个状态对应的字符串前面加字符，就能到达树上的儿子（因为树上一个状态的祖先节点一定是这个状态的后缀），如果在前面删掉字符，就可以到达自己的父节点。 所以对于前缀1~p和前缀q的lca, 假设第p个字符的时候建立的那个点x和加入q的时候的点y， lca(x, y)对应的状态，就是p,q的最长公共后缀。

  3. 这个树也是反串的后缀树（因为每个点往上跳fa就相当于从这个点对应的某个at(原串的位置），往前一个一个加字符，直到开头，对应到反串，就相当于是从某个字符开始，一个一个从后加字符，直到最后）（每到达终点节点就代表走到了末尾）， 每条边就是把从p的最长->q的最长字符串，需要依次在前面加入的边。 每个点出发的所有边的首字母一定是不一样的（否则就会出现两个状体接受同一个字符串）

  4. 每个点父亲的len比自己小

  5. 拿一个串T在S上跑，就能找到T的最长的后缀，使得它是S的字串。（本质上是T的每个前缀的这个值都求出来，在上一个前缀的基础上求下一个前缀）

    假设现在来到了T的i前缀，最长后缀长度是x, 所在节点是p. c是T[i+1]. 如果p有c的转移边,那就转移到这个点,并x++.

    否则就p不断跳fa(相当于删掉前面匹配的若干个字符), 直到遇到有c的转移边,并将x最终修改为len[p] + 1

  6. 每个点的len实际上等于所有tr连接到它的点的len的最大值+1

应用

小写字母, 1e6

标签：fa,后缀,tr,len,fail,字符串,节点
From： https://www.cnblogs.com/strywr/p/18283442

相关文章

  • 字符串相似度算法完全指南：编辑、令牌与序列三类算法的全面解析与深入分析
    在自然语言处理领域，人们经常需要比较字符串，这些字符串可能是单词、句子、段落甚至是整个文档。如何快速判断两个单词或句子是否相似，或者相似度是好还是差。这类似于我们使用手机打错一个词，但手机会建议正确的词来修正它，那么这种如何判断字符串相似度呢？本文将详细介绍这个问题。字......
  • 字符和字符串（2）(sizeof和strlen)
    1.初识sizeof与strlen函数    sizeof：准确的讲，sizeof不算一个函数，确切的说，它应该是一个运算符。sizeof使用的文件头文件就是#include<stdio.h>,sizeof运算符计算的是一个变量在计算机空间所占内存，当你使用sizeof函数计算一个变量空间的大小时，把这个变量放在si......
  • 力扣：151.反转字符串里的单词【2023年7月3日学习记录】
     方法一：双指针1.先使用trim()方法删除单词字符串前后空格字符。2.用两个指针指向字符串末尾单词（一个快指针，一个慢指针)，快指针先向前移动，直到移动到空格字符停下来，然后截取从快指针到慢指针的单词到新开辟的字符串中。3.快指针再向前移动一位，同时将慢指针指向到快指针的位......
  • 字符串的处理
    提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录一、最简单的回文字符串二、单词倒叙三，单词倒叙二四，单词数五，首字母大写六、公共前缀六、连续相同字符统计七，C语言合法变量名一、最简单的回文字符串如果一个字符串逆序后与正序相同，那么称......
  • C#面：编程长度为10000的字符串，通过随机从a-z中抽取10000个字符组成
    使用C#中的Random类来生成随机字符，并使用StringBuilder类来构建字符串。以下是一个示例程序：usingSystem;usingSystem.Text;classProgram{staticvoidMain(){Randomrandom=newRandom();StringBuilderstringBuilder=newStringBuild......
  • 151.翻转字符串里的单词 卡码网：55.右旋转字符串
    151.翻转字符串里的单词卡码网：55.右旋转字符串 151.翻转字符串里的单词题目链接:151.反转字符串中的单词-力扣（LeetCode） Code:classSolution{public:  stringreverseWords(strings){​    //单词级翻转,而不是单词内翻转  ​......
  • 10.优化算法之字符串
    1.最长公共前缀14.最长公共前缀-力扣（LeetCode）classSolution{publicstaticStringlongestCommonPrefix(String[]strs){if(strs==null||strs.length==0){return"";}intlength=strs.length;for(inti=0;i&l......
  • 请编写函数fun，该函数的功能是：统一一含字符串中单词的个数，作为函数值返回。一行字符串
    /请编写函数fun，该函数的功能是：统一一含字符串中单词的个数，作为函数值返回。一行字符串在主函数中输入，规定所有单词由小写字母组成，单词之间由若干个空格格开，一行的开始没有空格。/#include<stdio.h>#include<time.h>#include<stdlib.h>#defineN200intfun(char*buff)......
  • java中处理字符串常用的api
    Java中String常用APIString类位于jdk中的java.lang.String包中publicintlength()获取字符串的长度(字符的个数)publiccharcharAt(intindex)获取某个索引位置的字符返回publicchar[]t......
  • 字符串
    之前就是史，重新来写，字符串还是有必要学的。KMP用于文本串匹配。其和暴力的区别在于失配后会从一个特定位置重新开始匹配而不是从头开始，从而节约时间。这个失配数组也就是\(nex_i\)表示\(S[\mathbf{1}\dotsi]\)的最长\(\mathtt{border}\)长度，建出来之后相当于一个自动机......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99