首页 > 编程语言 >字符串1 最基础的字符串算法

字符串1 最基础的字符串算法

时间：2023-01-29 22:57:29浏览次数：55  
标签：nxt Automaton int 基础 len fail 算法 字符串 include

Trie

很简单的东西，这里就不阐述了。

const int N = 400005 + 111;
struct Trie{
    int nxt[N][27], cnt;
    int vis[N];
    void init(){
        memset(nxt, 0, sizeof nxt);
        memset(vis, 0, sizeof vis);
        cnt = 0;
    }
    void insert(char *s){
        int len = strlen(s), u = 0;
        for(int i = 0; i < len; i ++){
            int c = s[i] - 'a' + 1;
            if(!nxt[u][c]) nxt[u][c] = ++cnt;
            u = nxt[u][c];
        }
        vis[u] = 1;
    }
    bool find(char *s){
        int len = strlen(s), u = 0;
        for(int i = 0; i < len; i ++){
            int c = s[i] - 'a' + 1;
            if(!nxt[u][c]) return false;
            u = nxt[u][c];
        }
        return vis[u];
    }
}trie;

KMP

用于单模板的字符串匹配问题，预处理是均摊 \(O(m)\) 的，匹配是均摊 \(O(n)\) 的。

朴素的算法是枚举起始位置，暴力匹配，时间复杂度是 \(O(m(n-1))\) 的，但是在随机数据下表现良好。

考虑优化。

定义失配函数 \(fail_i\) 为最长的前缀的长度，满足是其模板串的后缀。

\(t = "aabccseaabcc"\)

其各个前缀的 \(fail\) 函数为：

\(P_1 = 0,P_2 = 1,P_3 = 0,P_4 = 0, P_5 = 0, P_6 = 0, P_7 = 0\)

\(P_8 = 1, P_9 = 2, P_{10} = 3, P_{11} = 4, P_{12} = 5\)

剩下的就是改变暴力的方式，如果下一个字符不匹配暴力跳 \(fail\) 即可。

求 \(fail\) 函数本质上是自己匹配自己。

#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
#define _for(i, a, b) for(int i = (a); i <= (b); i ++)
const int N = 1e6 + 11;
char A[N], B[N]; int P[N];
void P_function(char *s, int len){
    P[0] = P[1] = 0;
    int j = 0;
    _for(i, 2, len){
        while(j and s[j+1] != s[i]) j = P[j];
        if(s[j+1] == s[i]) j++;
        P[i] = j;
    }
}
void MP(char *text, char *moban, int len1, int len2){
    int j = 0;
    _for(i, 1, len1){
        while(j and text[i] != moban[j+1]) j = P[j];
        if(text[i] == moban[j+1]) j++;
        if(j == len2){
            printf("%d\n", i - len2 + 1);
            j = P[j];// 继续匹配
        }
    }
}
int main(){
    scanf("%s", A+1);
    scanf("%s", B+1);
    int n = strlen(A+1), m = strlen(B+1);
    P_function(B, m);
    MP(A, B, n, m);
    _for(i, 1, m) printf("%d ", P[i]);
    puts("");
    return 0;
}

\(Aho Corasick Automaton\) （\(AC\) 自动机）

自动 \(AC\)。

把 \(KMP\) 的 \(fail\) 函数扔到 \(Tire\) 上即可。

具体的，对于一个节点 \(u\) ， \(fail_u\) 为 整个 \(Trie\) 树上的最深的节点，满足其是 \(u\) 代表的字符串的前缀与后缀。

为了简化 找 \(fail\) 的过程，我们可以对 \(nxt\) 数组，也就是 \(Trie\) 树进行改造。

具体的，对于一个原来不存在的 \(nxt[u][c]\) ，我们将其赋值为 不断跳 \(fail\) 指针，找到的第一个真实存在的 \(nxt[fail[\dots fail[u]]][c]\)。

因此我们在匹配时不用跳 \(fail\) 指针，大大缩短了时间，对于一个原来不存在的 \(nxt[u][c]\) 赋值，实际上就是 \(nxt[u][c] = nxt[fail[u]][c]\)。

其正确性显然

如果 \(nxt[fail[u]][c]\) 不是真实存在的，其值一定是 \(nxt[fail[fail[u]]][c]\)，以此类推，一定会指向真实的 \(nxt[fail[\dots fail[u]]][c]\) 或 \(0\)。

#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <cstdio>
#include <iostream>
using namespace std;
#define _for(i, a, b) for(int i = (a); i <= (b); i ++)
#define _rep(i, a, b) for(int i = (a); i >= (b); i ++)
const int N = 150 * 77;
struct Aho_Corsick_Automaton{
    int nxt[N][28], vis[N], fail[N];
    int cnt, tot[N];
    void init(){
        memset(nxt, 0, sizeof nxt);
        memset(vis, 0, sizeof vis);
        memset(fail, 0, sizeof fail);
        memset(tot, 0, sizeof tot);
        cnt = 1;
    }
    void insert(char *s, int id){
        int u = 1, len = strlen(s);
        _for(i, 0, len - 1){
            int c = s[i] - 'a' + 1;
            if(!nxt[u][c]) nxt[u][c] = ++cnt;
            u = nxt[u][c];
        }
        vis[u] = id;
    }
    void failure_function(){
        _for(i, 0, 26) nxt[0][i] = 1;
        queue<int> q; q.push(1);
        fail[1] = 0;
        while(!q.empty()){
            int u = q.front(); q.pop();
            _for(c, 1, 26){
                int v = nxt[u][c];
                if(!v){
                    nxt[u][c] = nxt[fail[u]][c];
                    continue;
                }
                fail[v] = nxt[fail[u]][c];
                q.push(v);
            }
        }
    }
    int appear;
    void find_text(char *s){
        appear = 0;
        int len = strlen(s), u = 1;
        _for(i, 0, len-1){
            int c = s[i] - 'a' + 1;
            int v = nxt[u][c];
            while(v > 1){
                if(vis[v]) 
                    appear = max(appear, ++tot[vis[v]]);
                v = fail[v];
            }
            u = nxt[u][c];
        }
    }
}Automaton;
char moban[155][77], text[1000000 + 11];
int main(){
    int n = 0;
    while(scanf("%d", &n) == 1 and n != 0){
        Automaton.init();
        _for(i, 1, n){
            scanf("%s", moban[i]);
            Automaton.insert(moban[i], i);
        }
        Automaton.failure_function();
        scanf("%s", text);
        Automaton.find_text(text);
        printf("%d\n", Automaton.appear);
        _for(i, 1, n){
            if(Automaton.appear == Automaton.tot[i])
                printf("%s\n", moban[i]);
        }
    }
    return 0;
}

练习

Remember the Word UVA 1401

题意

题目链接

给出一个由 \(S\) 个不同单词组成的字典和一个长字符串，把该长字符串分解为若干个单词的连接，有多少种方法？

\(1 \le |Len| \le 3\times10^{5}, 1 \le S \le 4000, 1 \le Len_i \le 100\)。

分析

考虑 \(dp\) 求解。

定义 \(f_i = sum\{ f_{i+len_x} | x \text{是} S[i \dots len_S] \text{的前缀} \}\)，边界条件为 \(f_{len_S+1} = 1\)。

找 \(x\) 实际上是在由模板串组成的 \(Trie\) 上匹配 \(S[i \dots len_S]\) 的过程。

时间复杂度为 \(O(100(Len_s + S))\)。

代码

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
const int mod = 20071027;
const int N = 400005 + 111;
struct Trie{
    int nxt[N][27], cnt;
    int c[N];
    void init(){
        memset(nxt, 0, sizeof nxt);
        memset(c, 0, sizeof c);
        cnt = 0;
    }
    void insert(char *s){
        int len = strlen(s), u = 0;
        for(int i = 0; i < len; i ++){
            int to = s[i] - 'a' + 1;
            if(!nxt[u][to]){
                nxt[u][to] = ++cnt;
            }
            u = nxt[u][to];
        }
        c[u] = len;
    }
    void query(char *s, int from, int to, vector<int> &r){
        int u = 0;
        for(int i = from; i <= to; i ++){
            if(s[i] == '\0') break;
            int v = s[i] - 'a' + 1;
            if(!nxt[u][v]) break;
            u = nxt[u][v];
            if(c[u]) r.push_back(c[u]);
        }
        return;
    }
}trie;
int n, F[300000 + 11];
char s1[300000 + 11], s2[300000 + 11];
int main(){
    int T = 0;
    while(scanf("%s", s1) == 1){
        scanf("%d", &n);
        memset(F, 0, sizeof F);
        trie.init();
        for(int i = 0; i < n; i ++){
            scanf("%s", s2);
            trie.insert(s2);
        }
        int n = strlen(s1) - 1;
        F[n + 1] = 1;
        for(int i = n; i >= 0; i --){
            vector<int>pufer;
            trie.query(s1, i, n, pufer);
            for(auto j:pufer){
                (F[i] += F[i + j]) %= mod;
            }
        }
        printf("Case %d: %d\n", ++T, F[0]);
    }
    return 0;
}

"strcmp()" Anyone? UVA 11732

题意

题目链接

\(strcmp()\) 的实现如下：

int strcmp(char *s, char *t)
{
    int i;
    for (i=0; s[i]==t[i]; i++)
        if (s[i]=='\0')
            return 0;
    return s[i] - t[i];
}

求 \(\sum_{i=1}^{n}\sum_{j=i+1}^{n} chk(strcmp(S_i,S_j))\)，其中 \(chk(strcmp(S_i,S_j))\) 为 \(strcmp(S_i,S_j)\) 的比较次数。

分析

扔到 \(Trie\) 树上，手玩一下即可发现规律（计算每个节点的贡献）。

代码

#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long lgt;
const lgt N = 4e6 + 11;
struct Trie{
	lgt ct[N], cnt;
	lgt h[N], to[N], w[N], nt[N];
	lgt ans, tot;
	void init(){
		memset(h, 0, sizeof h);
		memset(to, 0, sizeof to);
		memset(w, 0, sizeof w);
		memset(nt, 0, sizeof nt);
		memset(ct, 0, sizeof ct);
		ans = tot = cnt = 0;
	}
	void add(lgt x, lgt y, lgt z){
		nt[++tot] = h[x];
		h[x] = tot;
		w[tot] = z;
        to[tot] = y;
	}
	void insert(char *s){
		lgt u = 0, len = strlen(s);
		ct[u]++;
		for(lgt i = 0; i <= len; i ++){
			lgt c = (lgt)s[i], v = -1, ww;
			for(lgt j = h[u]; j; j = nt[j]){
				lgt To = to[j], W = w[j];
				if(W == c){
					v = To;
					break;
				}
			}
			if(v == -1){
				v = ++cnt;
				add(u, v, c);
			}
			u = v;
			ct[u]++;
		}
		return;
	}
	void DP(lgt u, lgt dep){
		if(h[u] == 0) {
			ans += ct[u] * (ct[u]-1) * dep;
			return;
		}
		lgt sum = 0;
		for(lgt i = h[u]; i; i = nt[i]){
			lgt y = to[i];
			sum += ct[y] * (ct[u] - ct[y]);
		}
		ans += sum / 2 * (dep * 2 + 1);
		for(lgt i = h[u]; i; i = nt[i]){
			lgt y = to[i];
			DP(y, dep+1);
		}
		return;
	}
	lgt out(){ans = 0; DP(0, 0); return ans;}
};
lgt n;
char word[N];
Trie trie;

int main() {
  	lgt kase = 0;
  	while(scanf("%lld", &n) == 1 && n) {
    	trie.init();
    	for(lgt i = 0; i < n; i++) {
      		scanf("%s", word);
      		trie.insert(word);
    	}
    	printf("Case %lld: %lld\n", ++kase, trie.out());
  	}
  	return 0;
}

Period SP263&UVA1328

题意

题目链接

对于给定字符串 \(S\) 的每个前缀，我们想知道它是否为周期串（周期串定义为由若干最小循环节拼接而成的字符串），若是，输出前缀长度和循环节数量。

分析

构造 \(fail\) 函数，考虑 \(fail_i\) 的性质（前缀等于后缀）。

代码

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define _for(i, a, b) for(int i = (a); i <= (b); i ++)
const int N = 1e6 + 11;
int P[N]; char r[N];
void failure_function(char *moban, int len){
    int j = 0; P[0] = P[1] = 0;
    _for(i, 2, len){
        while(j and moban[j+1] != moban[i]) j = P[j];
        if(moban[j+1] == moban[i]) j++;
        P[i] = j;
    }
}
int main(){
    int T = 0,n, kase = 0;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        scanf("%s", r+1);
        failure_function(r, n);
        printf("Test case #%d\n", ++kase);
        _for(i, 2, n){
            if(P[i] and i % (i - P[i]) == 0) printf("%d %d\n", i,  i / (i-P[i]));
        }
        puts("");
    }
    return 0;
}

Dominating Patterns UVA1449

题目

原题链接

分析

由于可能出现相同的字符串，开 \(vector\) 记录出现的字符串，统计答案时暴力跳 \(fail\) 统计即可。

代码

#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <queue>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
const int N = 155;
const int M = 77;
const int P = 1e6 + 11;
const int Q = 155 * 77;
struct Aho_Corasick_Automaton{
    int nxt[Q][28], fail[Q], cnt, tot[N], vis[Q], max_appear;
    map< int, vector<int> > ID;
    void init(){
        memset(nxt, 0, sizeof nxt);
        memset(fail, 0, sizeof fail);
        memset(vis, 0, sizeof vis);
        memset(tot, 0, sizeof tot);
        ID.clear();
        cnt = 1;
    }
    void insert(char *s, int id){
        int u = 1, len = strlen(s);
        _for(i, 0, len - 1){
            int c = s[i] - 'a' + 1;
            if(!nxt[u][c]) nxt[u][c] = ++cnt;
            u = nxt[u][c];
        }
        ID[u].push_back(id);
    }
    void failure_function(){
        _for(i, 1, 27) nxt[0][i] = 1;
        queue<int> q; q.push(1);
        int u = 1; fail[1] = 0;
        while(!q.empty()){
            int u = q.front(); q.pop();
            _for(i, 1, 26){
                static int c, v;
                c = i; v = nxt[u][c];
                if(!nxt[u][c]){
                    nxt[u][c] = nxt[fail[u]][c];
                    continue;
                }
                fail[v] = nxt[fail[u]][c];
                q.push(v);
            }
        }
    }
    void find_text(char *s){
        int u = 1, len = strlen(s);
        max_appear = 0;
        _for(i, 0, len-1){
            int c = s[i] - 'a' + 1;
            int v = nxt[u][c];
            while(v > 1){
                if(ID.count(v)){
                    for(auto j:ID[v]){
                        tot[j]++;
                        max_appear = max(max_appear, tot[j]);
                    }
                }
                v = fail[v];
            }
            u = nxt[u][c];
        }
    }
}AC_Automaton;
char moban[N][M], text[P];
int main(){
    int n;
    while(scanf("%d", &n) == 1 and n != 0){
        AC_Automaton.init();
        _for(i, 1, n){
            scanf("%s", moban[i]);
            AC_Automaton.insert(moban[i], i);
        }
        scanf("%s", text);
        AC_Automaton.failure_function();
        AC_Automaton.find_text(text);
        printf("%d\n", AC_Automaton.max_appear);
        _for(i, 1, n){
            if(AC_Automaton.max_appear == AC_Automaton.tot[i]){
                printf("%s\n", moban[i]);
            }
        }
    }
    return 0;
}

Substring UVA11468

题目

题目链接

分析

直接建立 \(ACAM\) ，\(DP\) 计算答案即可。

daima

#include <queue>
#include <map>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <cstdio>
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
const int N = 4e4 + 5;
int Is(char c){
	if(isdigit(c)) return c - '0';
	else if(islower(c)) return c - 'a' + 11;
	else return c - 'A' + 37;
}
struct Aho_Corsick_Automaton{
    int nxt[N][77], cnt;
    int fail[N];
    bool vis[N];
    double f[N][200];
    double p[77];
    bool h[N][200];
    void init(){
        memset(nxt, 0, sizeof nxt);
        memset(vis, 0, sizeof vis);
        memset(fail, 0, sizeof fail);
        memset(f, 0, sizeof f);
        memset(p, 0, sizeof p);
        memset(h, 0, sizeof h);
        cnt = 1;
    }
    void insert(char *s){
        int u = 1, len = strlen(s);
        _for(i, 0, len - 1){
            int c = Is(s[i]);
            if(!nxt[u][c])nxt[u][c] = ++cnt;
            u = nxt[u][c];
        }
        vis[u] = 1;
    }
    void failure_function(){
        _for(i, 0, 70) nxt[0][i] = 1;
        queue<int> q; q.push(1);
        fail[1] = 0;
        while(!q.empty()){
            int u = q.front();
            q.pop();
            _for(i, 0, 70){
                int c = i, v = nxt[u][c];
                if(!v){
                    nxt[u][c] = nxt[fail[u]][c];
                    continue;
                }
                fail[v] = nxt[fail[u]][c];
                q.push(v);vis[u] |= vis[fail[u]];
            }
        }
    }
    double dfs(int now, int len){
        if(len == 0) return 1.0;
        if(h[now][len] == true)
            return f[now][len];
        double &ans = f[now][len];
        h[now][len] = true;
        ans = 0.000;
        _for(i, 0, 70){
            if(vis[nxt[now][i]]) continue;
            ans += p[i] * dfs(nxt[now][i], len-1);
        }
        return ans;
    }
}AC_Automaton;
char moban[1111];
int main(){
    int T, kase = 0;
    cin >> T;
    while(T--){
        AC_Automaton.init();
        int n, k, l;
        cin >> n;
        _for(i, 1, n){
            scanf("%s", moban);
            AC_Automaton.insert(moban);
        }
        AC_Automaton.failure_function();
        cin >> k;
        _for(i, 1, k){
            char c;
            double p;
            cin >> c >> p;
            AC_Automaton.p[Is(c)] = p;
        }
        cin >> l;
        printf("Case #%d: %.6lf\n", ++kase, AC_Automaton.dfs(1, l));
    }
    return 0;
}

标签：nxt,Automaton,int,基础,len,fail,算法,字符串,include
From： https://www.cnblogs.com/dadidididi/p/17074031.html

相关文章

  • C语言算法与数据结构[2023-01-29]
    C语言算法与数据结构[2023-01-29]算法与数据结构大作业(2022—2023学年第1学期）学院电子信息工程学院专业班级电信20-2班学号202005010209......
  • HLSL基础语法
    HLSL着色器由变量和函数组成，函数又由语句组成，它的语法和c++十分相似变量​ HLSL变量类似于c++中的变量，具有命名限制、取决于声明它们的位置的范围属性、标准数据类型，不同......
  • C语言数据结构与算法分析课程设计题目[2023-01-29]
    C语言数据结构与算法分析课程设计题目[2023-01-29]2021-2022学年第一学期数据结构与算法分析课程设计题目课程设计总体要求：课程设计报告撰写内容包括：题目分析；概要设......
  • Pandas字符串离散化处理
    字符串离散化处理importpandasaspdimportnumpyasnpfrommatplotlibimportpyplotasplt#读取csv文件file_path="./IMDB-Movie-Data.csv"df=pd.read_csv......
  • Redis缓存基础知识(一)
    一、基本概念1.Redis：属于开源的、键值对型的数据存储系统。支持网络、可基于内存、可持久化的日志型数据库。它可用作数据库、缓存、消息中间件。2.分析：正因为Redis是......
  • 算法刷题 Day 25 | 216.组合总和III 17.电话号码的字母组合
    今日内容：组合总和III电话号码的字母组合详细布置216.组合总和III如果把组合问题理解了，本题就容易一些了。题目链接/文章讲解：https://programmercarl.com/......
  • linux驱动移植-linux网卡驱动基础
    一、OSI七层模型1.1、概念OSI七层模式是一个标准，规定了各种计算机在世界范围内互联成网的标准框架，OSI模型是一个分层的模型，每一个部分称为一层，每一层扮演固定的角色，互不......
  • JS基础知识
    1.简单数据类型  1.1字符串型String   1.1.1字符串长度        1.1.2字符串拼接            1.1.3字符串拼接加强 ......
  • 【TS】基础类型
    在ts中定义基础类型，语法：let变量名：数据类型=值//布尔类型----booleanletflag:boolean=trueflag=false在赋值的时候，不能赋值定义外的数据......
  • 算法刷题 Day 24 | 回溯的理论基础 & 77. 组合
    今日内容：理论基础77.组合详细布置理论基础其实在讲解二叉树的时候，就给大家介绍过回溯，这次正式开启回溯算法，大家可以先看视频，对回溯算法有一个整体的了解......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99