首页 > 其他分享 >字符串（长期）

字符串（长期）

时间：2024-08-18 11:53:33浏览次数：7  
标签：长期 ch int long 字符串 节点 define

字符串

序言

字符串说实话我不算是很擅长，但是我还是想写一点东西。

字符串是一种存储字符的数据结构，本身来说这个并不难，但是因此也拓展出了非常非常多的算法。

很多人学习字符串的基本算法时就被劝退了，但殊不知这只是字符串的起点。

所以，坚持地学习下去吧，等你有一天层次高了后，你会发现：我以前怎么连这么弱智的算法都不会。

本人也是刚接触字符串不久，所以并不会涉及太难的知识点。

KMP

KMP 是字符串匹配算法中的经典，它同时由三位作者提出，故它的名字就是这三个人的名字首字母。

KMP 的精髓就是一个失配数组 \(fail[i]\)，但很多人一开始一直搞不懂这个数组的意义，所以我们不妨假设我们现在已经得到了这么一个数组，怎么去匹配呢？

我们先正常遍历，若发现一个不匹配的，我们就回退到上一个匹配的位置，直到找到一个匹配的位置。

但这样做有一个问题，就是回退的位置太远了，我们可以用失配数组来优化这个过程。

我们可以发现，失配数组 \(fail[i]\) 记录的是前缀的最长匹配长度，也就是说，如果我们已经匹配到位置 \(i\)，而后面还有一段字符串 \(s[j:j+m]\)，且 \(s[j:j+m]\) 与 \(s[i:i+m]\) 前缀相同，那么 \(fail[i]\) 就记录了 \(s[j:j+m]\) 的最长匹配长度。

那么，我们就可以根据失配数组来优化回退的位置。

这里因为笔者觉得 KMP 其实在省选难度并不会出现（一般都是 AC自动机或者马拉车等），所以就不展开讲解了。

这里放个模板

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define PII pair<int,int>
#define mk(a,b) make_pair(a,b)
using namespace std;
template<typename P>
inline void read(P &x){
    P res=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        res=res*10+ch-'0';
        ch=getchar();
    }
    x=res*f;
}
int T=1;
char a[1000010],b[1000010];
int nxt[1000010];
signed main(){
    cin>>a+1;
    cin>>b+1;
    int j=0;
    int la=strlen(a+1),lb=strlen(b+1);
    for(int i=2;i<=lb;++i){
        while(j && b[j+1]!=b[i]) j=nxt[j];
        if(b[j+1]==b[i]) j++;
        nxt[i]=j;
    }
    j=0;
    for(int i=1;i<=la;++i){
        while(j && b[j+1]!=a[i]) j=nxt[j];
        if(b[j+1]==a[i]) j++;
        if(j==lb){
            cout<<i-lb+1<<endl;
            j=nxt[j];
        }
    }
    for(int i=1;i<=lb;++i) cout<<nxt[i]<<' ';
    cout<<endl;
    return 0;
}

trie树

trie树是一种树形结构，用来存储字符串，它是一种非常经典的字符串匹配算法。

trie树的每个节点都是一个字符，如果当前字符不存在，则创建一个新的节点，如果存在，则进入这个节点。

具体来说，我们先判断当前节点 \(u\) 是否有儿子 \(ch\)，即新插入的字符，如果有，则令 \(u=t[u].son[ch]\)，代表当前节点沿着树边向下移，如果没有，则新创一个节点 \(t[u].son[ch]=++cnt\)，然后还是 \(u=t[u].son[ch]\)，代表当前节点沿着树边向下移。这样就能实现插入的操作。

然后，我们要查询一个字符串是否在trie树中，我们从根节点开始，沿着树边向下，如果当前节点的儿子中有某个儿子的字符与查询字符串的当前字符相同，则继续沿着这个儿子的边向下，如果没有，则说明这个字符不在trie树中，返回false。

如果查询到最后一个字符，则说明这个字符串在trie树中，返回true。

trie树的插入以及查询时间复杂度均为 \(O(m)\)，其中 \(m\) 为字符串的长度。

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define PII pair<int,int>
#define mk(a,b) make_pair(a,b)
using namespace std;
template<typename P>
inline void read(P &x){
    P res=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        res=res*10+ch-'0';
        ch=getchar();
    }
    x=res*f;
}
int T=1;
struct node{
    int a[72];
    int flag;
}t[3000010];
string a;
int n,m;
int u,cnt=0;
int get(char a){
    if(a>='A' && a<='Z') return (int)(a-'A');
    else if(a>='a' && a<='z') return (int)(a-'a'+26);
    else return (int)(a-'0'+52);
}
void insert(string s){
    int len=s.size();
    u=0;
    s='0'+s;
    for(int i=1;i<=len;++i){
        int k=get(s[i]);
        if(!t[u].a[k]) t[u].a[k]=++cnt;
        u=t[u].a[k];
        t[u].flag++;
    }
}
int query(string s){
    int len=s.size();
    u=0;
    s='0'+s;
    for(int i=1;i<=len;++i){
        int k=get(s[i]);
        if(!t[u].a[k]) return 0;
        u=t[u].a[k];
    }
    return t[u].flag;
}
signed main(){
    auto solve=[&](){
        read(n),read(m);
        for(int i=0;i<=cnt;++i) for(int j=0;j<=70;++j) t[i].a[j]=0;
        for(int i=0;i<=cnt;++i) t[i].flag=0;
        cnt=0;
        for(int i=1;i<=n;++i){
            cin>>a;
            insert(a);
        }
        for(int i=1;i<=m;++i){
            cin>>a;
            cout<<query(a)<<endl;
        }
    };
    //freopen(.in,'r',stdin);
    //freopen(.out,'w',stdout);
    read(T);
    while(T--) solve();
    return 0;
}

AC自动机

AC自动机是一种字符串匹配算法，它是基于trie树的改进，它可以解决一些trie树无法解决的问题。

AC自动机可以说是 KMP 与 trie树 的结合体，它在trie树的基础上，增加了一些状态转移的规则，使得它可以更好地匹配字符串。

具体来说，KMP 只能处理匹配单个字符串的问题，一旦有 \(n\) 个字符串需要查找，复杂度上升为 \(O(nm)\)，而 AC自动机 就可以解决这个问题。

我们还是对每个字符串建 trie树，然后我们需要一个链接边，类似 KMP 的，它的目标我们设为 \(fail[u]\) 表示的是从根节点到 \(u\) 所形成的字符串的最长公共前后缀的节点（就是 KMP 中的 \(fail\) 的定义），这样我们就可以根据这个链接边来优化回退的位置。

AC自动机的状态转移规则如下：

  • 如果当前字符与当前节点的字符相同，则进入当前节点的儿子，并将当前节点设为 \(fail[u]\)；
  • 如果当前字符与当前节点的字符不同，则沿着当前节点的链接边，找到第一个与当前字符相同的节点，并将当前节点设为 \(fail[u]\)；
  • 如果当前字符与当前节点的字符相同，但当前节点的儿子中没有与当前字符相同的儿子，则说明当前字符不在当前节点的子树中，则沿着当前节点的链接边，找到第一个与当前字符相同的节点，并将当前节点设为 \(fail[u]\)；

这样，我们就可以根据 \(fail\) 数组来优化回退的位置。

AC自动机的插入与查询时间复杂度均为 \(O(26n+m)\)，其中 \(m\) 为字符串的长度。

代码（二次加强版）如下：

#include<bits/stdc++.h>
#define ull unsigned long long
#define PII pair<int,int>
#define mk(a,b) make_pair(a,b)
using namespace std;
template<typename P>
inline void read(P &x){
    P res=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        res=res*10+ch-'0';
        ch=getchar();
    }
    x=res*f;
}
int T=1;
struct node{
    int a[27];
    int flag;
    int ans;
    node(){
        memset(a,0,sizeof(a));
        flag=0;
        ans=0;
    }
}trie[2000010];
int n;
string t;
string s;
int u,cnt=0;
int fail[2000010],vis[200010],in[20000010],pp[2000001];
int get(char a) {return (int)(a-'a');}
queue<int> q;
void insert(string s,int id){
    int len=s.size();
    s='0'+s;
    u=0;
    for(int i=1;i<=len;++i){
        int k=get(s[i]);
        if(!trie[u].a[k]) trie[u].a[k]=++cnt;
        u=trie[u].a[k];
    }
    if(!trie[u].flag) trie[u].flag=id;
    pp[id]=trie[u].flag;
}
void build(){
    for(int i=0;i<26;++i) if(trie[0].a[i]) q.push(trie[0].a[i]);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<26;++i){
            int v=trie[u].a[i];
            if(v) fail[v]=trie[fail[u]].a[i],in[fail[v]]++,q.push(v);
            else trie[u].a[i]=trie[fail[u]].a[i];
        }
    }
}
void topo(){
    for(int i=1;i<=cnt;++i) if(in[i]==0) q.push(i);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[trie[u].flag]=trie[u].ans;
        int v=fail[u];in[v]--;
        trie[v].ans+=trie[u].ans;
        if(in[v]==0) q.push(v);
    }
}
void query(string s){
    int len=s.size();
    s='0'+s;
    u=0;
    for(int i=1;i<=len;++i){
        int p=get(s[i]);
        u=trie[u].a[p];
        trie[u].ans++;
    }
}
signed main(){
    auto solve=[&](){
        read(n);
        for(int i=1;i<=n;++i) cin>>t,insert(t,i);
        build();
        cin>>s;
        query(s);
        topo();
        for(int i=1;i<=n;++i) cout<<vis[pp[i]]<<endl;
    };
    //freopen(.in,'r',stdin);
    //freopen(.out,'w',stdout);
    //read(T);
    while(T--) solve();
    return 0;
}

拓展KMP（Z函数）

其实这个我不是很理解与 KMP 有什么关系，但是这个我印象比较深。

Z函数的精髓是维护一个盒子，\(z_i\) 表示的是从 \(i\) 这个位置出发，设能拓展到的右端点为 \(r\) ，左端点为 \(l\)，\([l,r]\) 之间最长公共前缀的长度。

简单点理解就是：当前 \(i\) 能往后拓展到的盒子的最大长度，使得整个盒子中有最长公共前缀。

说以来比较绕口，举个例子：

img

我们先不管 \(nxt\) 函数有什么用，先看看它怎么求出来的。

我们假设 \(z[1]\) 至 \(z[i-1]\) 的函数值我们已知，现在求 \(z[i]\)，有个明显的结论：

\([1,z[i]-1],[l,l+z[i]-1]\) 是相同的，这里的 \(l\) 指的是盒子 \(z[i]\) 的左端点。如下图：

img

那么也有：

img

显然可以观察到，我们拓展 \(z[i]\) 时。若它当前在一个前面的 \(z[k]\) 所表示的盒子中，那么 \(z[i]\) 的大小就是 \(z[i-l]\)。

但是我们要考虑一个问题，有可能 \(z[i]\) 的大小会超出之前的 \(l,r\) 的范围，比如：

img

所以我们先不考虑超出的部分，那么 \(z[i]\) 的大小必须得限制在剩余的长度中，即 \(z[i]=min(z[i-l],r-i+1)\)。

现在考虑超出的部分或者本身 \(i\) 就不在 \([l,r]\) 范围内的情况，那么 \(z[i]\) 的大小就没有前继可以转移了，直接暴力：

while(a[z[i]]==a[i+z[i]] && i+z[i]<n) z[i]++;

最后我们还要移动 \(l\) 和 \(r\) 的位置来更新后面的 \(z\) 函数。

所以当当前的 \(z[i]\) 超出范围时，我们就要更新 \(l\) 和 \(r\) 的位置，
即：

if(i+z[i]>r) l=i,r=i+z[i];

这样就得到了 \(z\) 函数。

但是其实我到现在都没有遇到需要用 \(z\) 函数解决的题（不如后缀自动机）。

代码如下：

void getz(string a){
    n=a.size();
    for(int i=1,l=0,r=0;i<n;++i){
        if(i<r) z[i]=min(z[i-l],r-i);
        while(a[z[i]]==a[i+z[i]] && i+z[i]<n) z[i]++;
        if(i+z[i]>r) l=i,r=i+z[i];
    }
}

Manacher马拉车

求解回文子串的一种算法，用的不多，一般都用回文自动机（PAM）或者后缀数组啥的。

其实跟 \(z\) 函数几乎一模一样，只需要把 \(z[i]\) 所代表的意义变成：以 \(i\) 为回文中心的最长回文半径（包含自身）。

代码也是高度相似：

void manacher(char *s,int n){
    d[1]=1;
    for(int i=2,l,r=1;i<=n;++i){
        if(i<=r) d[i]=min(d[r-i+l],r-i+1);
        while(s[i-d[i]]==s[i+d[i]]) d[i]++;
        if(i+d[i]-1>r) l=i-d[i]+1,r=i+d[i]-1;
    }
}

建议读者自己理解一下，理解不了的话建议去 Bilibili找董晓算法学习。

后缀数组（SA）

现在我只学习了后缀数组排序算法，实际运用还没学。

后缀排序可以在 \(O(n\log n)\) 的时间内求出后缀数组关联的两个数组 \(rk[i]\) 和 \(sa[i]\)，其中 \(rk[i]\) 表示的是 \(i\) 位置的后缀的排名，\(sa[i]\) 表示的是排名为 \(rk[i]\) 的后缀在原串中的位置。二者相互映射，即 \(sa[rk[i]]=rk[sa[i]]\)。

具体思路就是倍增一个长度 \(k\)，然后用 \(k\) 作为步长，对原串进行分块，对每个块进行排序，得到的结果就是后缀数组。

排序的过程就是基数排序，没学的自己去学，我不讲基础的。

同时，还可以求出 LCP 数组，即 \(lcp[i]\) 表示的是 \(i\) 位置的后缀与 \(i+1\) 位置的后缀的最长公共前缀的长度。

但是在模板中并没有对 \(lcp\) 数组的运用：

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define PII pair<int,int>
#define mk(a,b) make_pair(a,b)
using namespace std;
template<typename P>
inline void read(P &x){
    P res=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        res=res*10+ch-'0';
        ch=getchar();
    }
    x=res*f;
}
int T=1;
const int N=2e6+10;
char s[N];
int n,m;
int x[N],y[N],sa[N],rk[N],h[N];
int c[N];
void getsa(){
    int i,k;
    for(i=1;i<=n;++i) c[x[i]=s[i]]++;
    for(i=1;i<=m;++i) c[i]+=c[i-1];
    for(i=n;i>=1;--i) sa[c[x[i]]--]=i;
    for(k=1;k<=n;k<<=1){
        //第二关键字排序
        memset(c,0,sizeof(c));
        for(i=1;i<=n;++i) y[i]=sa[i];
        for(i=1;i<=n;++i) c[x[y[i]+k]]++;
        for(i=1;i<=m;++i) c[i]+=c[i-1];
        for(i=n;i>=1;--i) sa[c[x[y[i]+k]]--]=y[i];
        //第一关键字排序
        memset(c,0,sizeof(c));
        for(i=1;i<=n;++i) y[i]=sa[i];
        for(i=1;i<=n;++i) c[x[y[i]]]++;
        for(i=1;i<=m;++i) c[i]+=c[i-1];
        for(i=n;i>=1;--i) sa[c[x[y[i]]]--]=y[i];
        //重排
        for(i=1;i<=n;++i) y[i]=x[i];
        for(m=0,i=1;i<=n;++i){
            if(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) x[sa[i]]=m;
            else x[sa[i]]=++m;
            if(m==n) break;
        }
    } 
}
void geth(){
    for(int i=1;i<=n;++i) rk[sa[i]]=i;
    for(int i=1,k=0;i<=n;++i){
        if(rk[i]==1) continue;
        if(k) k--;
        int j=sa[rk[i]-1];
        while(i+k<=n && j+k<=n && s[i+k]==s[j+k]) k++;
        h[rk[i]]=k;
    }
}
signed main(){
    scanf("%s",s+1);
    n=strlen(s+1);m=122;
    getsa();
    // geth();
    for(int i=1;i<=n;++i) printf("%d ",sa[i]);
    printf("\n");
    return 0;
}

标签：长期,ch,int,long,字符串,节点,define
From： https://www.cnblogs.com/lizihan00787/p/18361413

相关文章

  • 代码随想录 day 54 字符串接龙 | 有向图的完全可达性 | 岛屿的周长
    字符串接龙字符串接龙解题思路利用每次更改一次的特性在字典中来找到符合条件的字符串，同时，我们利用set数据结构来筛选该字符串是否被访问过，同时记录到达该字符串所需要的路径长度知识点心得有向图的完全可达性有向图的完全可达性解题思路有向图和无向图的区别在于它的边......
  • 【C语言】字符函数和字符串函数
    文章目录前言一、字符分类函数二、字符转换函数三、字符串函数的分类四、strlen函数的使用五、strcpy和strncpy函数的使用1.strcpy2.strncpy六、strcat和strncat函数的使用1.strcat2.strncat七、strcmp和strncmp函数的使用1.strcmp2.strncmp八、strstr函数的使用九、s......
  • 回调函数，字符函数，字符串函数
    前言：上一趴我们学习了指针。那么今天我们来学习新的知识，回调函数，字符函数，字符串函数。1回调函数什么是回调函数呢？回调函数就是通过函数指针调用的函数。如果你把函数的指针（地址）作为参数传递给另一个函数，当这个指针被用来调用其所指向的函数时，被调用的函数就是回调函数。......
  • Python之字符串例题2道
    实例1：记录成绩实例2：回文实例1：记录成绩将语文数学英语的成绩一次性输入，用空格隔开，例如“899690”利用split()函数可以对字符串以指定的字符进行切割，这里括号内没有指定字符，默认以空格作为切割标志。如score=input().split()会得到一个列表[89,96,90]然后再通......
  • 代码随想录算法训练营day09|151.翻转字符串里的单词，卡码网：55.右旋转字符串，28.实现 str
    151.翻转字符串里的单词题目链接：https://leetcode.cn/problems/reverse-words-in-a-string/description/暴力removeExtraSpaces：voidremoveExtraSpaces(string&s){for(inti=s.size()-1;i>0;i--){if(s[i]==''&&s[i]=......
  • PTA 7-30 字符串的冒泡排序
    7-30字符串的冒泡排序（20分）我们已经知道了将N个整数按从小到大排序的冒泡排序法。本题要求将此方法用于字符串序列，并对任意给定的K（<N），输出扫描完第K遍后的中间结果序列。输入格式：输入在第1行中给出N和K（1≤K<N≤100），此后N行，每行包含一个长度不超过10的、仅由小写英文字母组成的......
  • 力扣面试经典算法150题：找出字符串中第一个匹配项的下标
    找出字符串中第一个匹配项的下标今天的题目是力扣面试经典150题中的数组的简单题:找出字符串中第一个匹配项的下标题目链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/?envType=study-plan-v2&envId=top-interview-......
  • 字符串比较的常用函数
    staticvoidMain(string[]arg){intint1=0;intint2=0;intint3=0;stringstr1="adf";stringstr2="adf";stringstr3="Adf";......
  • JAVA 解析html 类型字符串（使用jsoup）
    1.引入pom文件<dependency><groupId>org.jsoup</groupId><artifactId>jsoup</artifactId><version>1.17.2</version></dependency>2.使用在线解析html工具，自己先看清html内容 （在线推荐:https://coding.tools/cn/html-beautifier#googl......
  • C:一个字符数组里面解析出多个字符串
    一个字符数组里面存放了多个字符串，每个字符串以‘\0’。要求把这些有效字符串筛选出来并输出。 扩展：'\0\0'表示字符串结束。V2方法就是实现的这个扩展功能。 #include<stdio.h>#include<string.h>#include<malloc.h>voidprintSzNameList(charszNameList[],in......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99