[原创]字符串问题 —模板（不定期更新中。）

2016-08-08 13:20:00 Tabris_ 阅读数：845

博客爬取于2020-06-14 22:39:14
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52151010

#KMP

算法介绍文章：http://blog.csdn.net/u011564456/article/details/20862555?utm_source=tuicool&utm_medium=referral

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
char s1[N],s2[N];
int Next[N];//Next[i] 表示从[0~i]中最长公共前缀的长.
void get_next(char *s,int len){
    for(int i=0,j=-1;i<=len;++i,++j){
        Next[i]=j;
        while(j>=0&&s[i]!=s[j]) j = Next[j];
    }
//    for(int i=0;i<=len;i++) printf("%d%c",Next[i],(i==len)?'\n':' ');
}
//在串s上找sz
int KMP (char *s,int len,char *sz,int l){
    int i=0,j=0,cnt=0;
    while(i<len/*&&j<l*/){
        if(s[i]==sz[j])  i++,j++;
        else{
            if(0==j)  i++;
            else      j=Next[j];
        }
        if(j==l) cnt++;
    }

//   return (j==l)?(i-l+1):-1; //找第一次出现的位置
    return cnt; //找出现的个数
}
/*
            for(int j=0,i=0;i<=len;i++,j++){
                ans ^= 1LL*(j)*(j)*(len-k-j)*(i-j) ;
                while(j>=0&&a[i]!=p[j]) j=Next[j];
            }
*/

字典树

实现方法1

指针动态实现

Tree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//#include <bits/stdc++.h>
# include <iostream>
# include <stdio.h>
# include <string.h>
# include <algorithm>

using namespace std;

# define LL long long int
# define lalal puts("********");

const int N = 1010101;
const int Max = 26;

typedef struct node
{
    struct node *next[Max];
    int num;
}Node;

//创建一个新节点
Node *createNew()
{
    Node *p=new Node;
    for(int i=0;i<Max;i++)
        p->next[i]=NULL;

    p->num=0;
    return p;
}
Node *head;

//插入一个字符串
void Insert_str(char str[])
{
    int len=strlen(str);
  //  printf("len = %d--  ",len);
    Node *t,*p=head;
    for(int i=0;i<len;i++)
    {
        int c=str[i]-'a';
        if( p->next[c] == NULL )
        {
            //lalal
            t=createNew();
            p->next[c]=t;
        }
        p=p->next[c];
        p->num++;
       // cout<<p->num<<"-"<<str[i]<<" ";
    }
}

int Search_str(char str[])
{
    Node *p=head;
    int len=strlen(str);

    int counts=0;
    for(int i=0;i<len;i++)
    {
        int c=str[i]-'a';
        if(p->next[c]==NULL)
        {
        //  cout<<"不存在字符串"<<endl;
            counts=0;
            return 0;
        }
        else
        {
            p=p->next[c];
            counts=p->num;
            //printf("%d ",p->num);
        }
    }
    return counts;
}


int main()
{
    head = createNew();
    char s[11];
    while(gets(s)&&s[0]!='\0') {Insert_str(s);} //一直读入数据，直到遇到空字符串
    while(gets(s))
        printf("%d\n",Search_str(s));
    return 0;

}

实现方法2

数组静态实现
(Double Arrays Trie-DAT)
用两个数组来实现
其实本质来看，就和模拟数组差不多少的东西，每次将元素放到尾部。
再用另一个二位数组来表示接下来的索引就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int N = 100000+7;
int a[N][字符种类数],f[N],cnt = 0;

//插入
inline void insert(String str){
	int  len = str.length(),now = 0;
	for(int i=0;i<len;++i){
		if(!a[now][str[i]-'a']) a[now][str[i]-'a'] = ++cnt;
		now = a[now][str[i]-'a'];
		++f[now];
	}
	return ;
}


AC自动机

讲义+例题
讲解1
讲解2

实现方法1

指针动态存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
# include<iostream>
# include<string.h>
# include<malloc.h>
# include <queue>
using namespace std;

typedef struct node{
    struct node *next[26];  //接收的态
    struct node *par;   //父亲节点
    struct node *fail;  //失败节点
    char inputchar;
    int patterTag;    //是否为可接收态
    int patterNo;   //接收态对应的可接受模式
}*Tree,TreeNode;
char pattern[4][30]={"nihao","hao","hs","hsr"};

/**
申请新的节点，并进行初始化
*/
TreeNode *getNewNode()
{
    int i;
    TreeNode* tnode=(TreeNode*)malloc(sizeof(TreeNode));
    tnode->fail=NULL;
    tnode->par=NULL;
    tnode->patterTag=0;
    for(i=0;i<26;i++)
        tnode->next[i]=NULL;
    return tnode;
}

/**
将Trie树中，root节点的分支节点，放入队列
*/
int  nodeToQueue(Tree root,queue<Tree> &myqueue)
{
    int i;
    for (i = 0; i < 26; i++)
    {
        if (root->next[i]!=NULL)
            myqueue.push(root->next[i]);
    }
    return 0;
}

/**
建立trie树
*/
Tree buildingTree()
{
    int i,j;
    Tree root=getNewNode();
    Tree tmp1=NULL,tmp2=NULL;
    for(i=0;i<4;i++)
    {
        tmp1=root;
        for(j=0;j<strlen(pattern[i]);j++)   ///对每个模式进行处理
        {
            if(tmp1->next[pattern[i][j]-'a']==NULL) ///是否已经有分支，Trie共用节点
            {
                tmp2=getNewNode();
                tmp2->inputchar=pattern[i][j];
                tmp2->par=tmp1;
                tmp1->next[pattern[i][j]-'a']=tmp2;
                tmp1=tmp2;
            }
            else
                tmp1=tmp1->next[pattern[i][j]-'a'];
        }
        tmp1->patterTag=1;
        tmp1->patterNo=i;
    }
    return root;
}

/**
建立失败指针
*/
int buildingFailPath(Tree root)
{
    int i;
    char inputchar;
    queue<Tree> myqueue;
    root->fail=root;
    for(i=0;i<26;i++)   ///对root下面的第二层进行特殊处理
    {
        if (root->next[i]!=NULL)
        {
            nodeToQueue(root->next[i],myqueue);
            root->next[i]->fail=root;
        }
    }

    Tree tmp=NULL,par=NULL;
    while(!myqueue.empty())
    {
        tmp=myqueue.front();
        myqueue.pop();
        nodeToQueue(tmp,myqueue);

        inputchar=tmp->inputchar;
        par=tmp->par;

        while(true)
        {
            if(par->fail->next[inputchar-'a']!=NULL)
            {
                tmp->fail=par->fail->next[inputchar-'a'];
                break;
            }
            else
            {
                if(par->fail==root)
                {
                    tmp->fail=root;
                    break;
                }
                else
                    par=par->fail->par;
            }
        }
    }
    return 0;
}

/**
进行多模式搜索，即搜寻AC自动机
*/
int searchAC(Tree root,char* str,int len)
{
    TreeNode *tmp=root;
    int i=0;
    while(i < len)
    {
        int pos=str[i]-'a';
        if (tmp->next[pos]!=NULL)
        {
            tmp=tmp->next[pos];
            if(tmp->patterTag==1)    ///如果为接收态
            {
                cout<<i-strlen(pattern[tmp->patterNo])+1<<'\t'<<tmp->patterNo<<'\t'<<pattern[tmp->patterNo]<<endl;
            }
            i++;
        }
        else
        {
            if(tmp==root)
                i++;
            else
            {
                tmp=tmp->fail;
                if(tmp->patterTag==1)    //如果为接收态
                    cout<<i-strlen(pattern[tmp->patterNo])+1<<'\t'<<tmp->patterNo<<'\t'<<pattern[tmp->patterNo]<<endl;
            }
        }
    }
    while(tmp!=root)
    {
        tmp=tmp->fail;
        if(tmp->patterTag==1)
            cout<<i-strlen(pattern[tmp->patterNo])+1<<'\t'<<tmp->patterNo<<'\t'<<pattern[tmp->patterNo]<<endl;
    }
    return 0;
}

/**
释放内存，DFS
*/
int destory(Tree tree)
{
    if(tree==NULL)
        return 0;
    queue<Tree> myqueue;
    TreeNode *tmp=NULL;

    myqueue.push(tree);
    tree=NULL;
    while(!myqueue.empty())
    {
        tmp=myqueue.front();
        myqueue.pop();

        for (int i = 0; i < 26; i++)
        {
            if(tmp->next[i]!=NULL)
                myqueue.push(tmp->next[i]);
        }
        free(tmp);
    }
    return 0;
}

int main()
{
    char a[]="sdmfhsgnshejfgnihaofhsrnihao";
    Tree root=buildingTree();   ///建立Trie树
    buildingFailPath(root); ///添加失败转移
    cout<<"待匹配字符串："<<a<<endl;
    cout<<"模式"<<pattern[0]<<" "<<pattern[1]<<" "<<pattern[2]<<" "<<pattern[3]<<" "<<endl<<endl;
    cout<<"匹配结果如下："<<endl<<"位置\t"<<"编号\t"<<"模式"<<endl;
    searchAC(root,a,strlen(a)); ///搜索
    destory(root);  ///释放动态申请内存
    return 0;
}

实现方法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

const int MAXN = 300000+777;
template<class T>
struct AC_AUTO{
    map<T,int>mp[MAXN];
    typename map<T,int> :: iterator it;
    int fail[MAXN],val[MAXN],Q[MAXN],head,tail,root,cnt;
    void init(){
        cnt=0;
        root=newnode();
    }
    int newnode(){
        mp[cnt].clear();
        val[cnt++]=0;
        return cnt-1;
    }
    void insert(T s[],int n){
        int now=root;
        for(int i=0;i<n;i++){
            if(!mp[now].count(s[i]))
                mp[now][s[i]]=newnode();
            now=mp[now][s[i]];
        }
        val[now]++;
    }
    void build(){
        head=tail=0;
        fail[root]=root;
        for(it=mp[root].begin();it!=mp[root].end();++it){
            fail[it->second]=root;
            Q[tail++]=it->second;
        }
        while(head!=tail){
            int now=Q[head++];
            val[now]+=val[fail[now]];
            for(it=mp[now].begin();it!=mp[now].end();++it){
                int x=fail[now],flag=0;
                while(x!=root){
                    if(mp[x].count(it->first)){
                        fail[it->second]=mp[x][it->first];
                        flag=1;
                        break;
                    }
                    x=fail[x];
                }
                if(x==root && mp[x].count(it->first)){
                    fail[it->second]=mp[x][it->first];
                    flag=1;
                }
                if(!flag) fail[it->second]=root;
                Q[tail++]=it->second;
            }
        }
    }
    LL query(T s[],int n){
        LL ret=0;
        int now=root;
        for(int i=0;i<n;i++){
            int x=now,flag=0;
            while(x!=root){
                if(mp[x].count(s[i])){
                    now=mp[x][s[i]];
                    flag=1;
                    break;
                }
                x=fail[x];
            }
            if(x==root && mp[x].count(s[i])){
                now=mp[x][s[i]];
                flag=1;
            }
            if(!flag) now=root;
            ret+=val[now];
        }
        return ret;
    }
};
AC_AUTO<int> ac;

int a[N],b[N],n,m,len,x,pre;

int main(){
    ac.init();
	while(){
	    ac.insert(b,len);
    }
    ac.build();
    ans = ac.query(a,n-1);
    return 0;
}

Manacher

Manacher 是一个能在O(n)O(n)的复杂度内解决字符串中最长回文子串的问题

这篇帖子给的挺详细的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/***
str  原字符串
a    进行Manacher算法的为减轻编码难度改进的字符串
p[i] 以a[i]为中心的回文串的半径(含a[i])
id   最长回文子串的中心位置
mx   id+p[id] 最长回文子串的左外边界。

算法核心的部分
if(mx > i) p[i] = (p[(id<<1)-i]<(mx-i))?p[(id<<1)-1]:(mx-i);
else p[i]=1;

首先我们知道对于一个字符串进行操作的时候，是从左到右依次进行的
那么由于回文串的对称性，
那么可以确定的是对于a[i]为中心的回文串的长度至少是在以这个最大的回文串中对称的那个位置为中心的回文串的长度,但只能确定的是在最大的回文串的那一部分中的长度,至于之外的就要一个个的匹配了

*/
/***
id  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7
a： $ # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #
p_i 1 1 2 1 2 5 2

*/
char a[N],str[N];
int p[N];

void train(){
    int len  = 0;
    a[len] = '$', a[++len] = '#';
    int slen = strlen(str)-1;
    Rep(i,0,slen) a[++len] = str[i],a[++len] = '#';

    memset(p,0,sizeof(p));
    int id = -1,mx = -1,mxp = -1;
    Rep(i,0,len){
        if(mx > i) p[i] = (p[(id<<1)-i]<(mx-i))?p[(id<<1)-i]:(mx-i);
        else p[i]=1;
        while(a[i-p[i]]==a[i+p[i]]) p[i]++;
        if(p[i]+i>mx) mx=p[i]+i,id=i;
        if(p[i]>mxp) mxp = p[i];
    }
    printf("%d\n",mxp-1);
    return ;
}

后缀数组

SA[i] = j表示为按照从小到大排名为i的后缀 是以j（下标）开头的后缀

rank[i] = j 表示为按照从小到大排名 以i为下标开始的后缀 排名为j

RANK表示你排第几 SA表示排第几的是谁 （记住这个就行）

height[i] 表示 sa[i] 与 sa[i-1] 的最长公共前缀(LCP)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
const int MAXN=400010;
//以下为倍增算法求后缀数组
int wa[MAXN],wb[MAXN],wv[MAXN],Ws[MAXN];
int cmp(int *r,int a,int b,int l) {
    return r[a]==r[b]&&r[a+l]==r[b+l];
}
/**< 传入参数：str,sa,len+1,ASCII_MAX+1 */
void da(const int r[],int sa[],int n,int m) {
    int i,j,p,*x=wa,*y=wb,*t;
    for(i=0; i<m; i++) Ws[i]=0;
    for(i=0; i<n; i++) Ws[x[i]=r[i]]++;//以字符的ascii码为下标
    for(i=1; i<m; i++) Ws[i]+=Ws[i-1];
    for(i=n-1; i>=0; i--) sa[--Ws[x[i]]]=i;
    /*cout<<"SA"<<endl;;
    for(int i=0;i<n+1;i++)cout<<sa[i]<<' ';*/
    for(j=1,p=1; p<n; j*=2,m=p) {
        for(p=0,i=n-j; i<n; i++) y[p++]=i;
        for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;
        for(i=0; i<n; i++) wv[i]=x[y[i]];
        for(i=0; i<m; i++) Ws[i]=0;
        for(i=0; i<n; i++) Ws[wv[i]]++;
        for(i=1; i<m; i++) Ws[i]+=Ws[i-1];
        for(i=n-1; i>=0; i--) sa[--Ws[wv[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
    return;
}
int sa[MAXN],Rank[MAXN],height[MAXN];
//求height数组
/**< str,sa,len */
void calheight(const char *r,int *sa,int n) {
    int i,j,k=0;
    for(i=1; i<=n; i++) Rank[sa[i]]=i;
    for(i=0; i<n; height[Rank[i++]]=k)
        for(k?k--:0,j=sa[Rank[i]-1]; r[i+k]==r[j+k]; k++);
    // Unified  不要乱用，出来检查为了方便的时候 否则容易RE，WA
//    for(int i=n; i>=1; --i) ++sa[i],Rank[i]=Rank[i-1];

}

//求lcp(suffixal(i),suffixal(j))

int mm[MAXN],dp[MAXN][20];
void initrmq(int n,int b[]) {
    mm[0]=-1;
    for(int i=1; i<=n; i++) {
        mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
        dp[i][0]=b[i];
    }
    for(int j=1; j<=mm[n]; j++)
        for(int i=1; i+(1<<j)-1<=n; i++)
            dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}

int lcp(int x,int y) {
    x=Rank[x],y=Rank[y];
    if(x>y) swap(x,y); x++;
    int k=mm[y-x+1];
    return min(dp[x][k],dp[y-(1<<k)+1][k]);
}

char s[N];
int a[N];

int main(){
    scanf("%s",s);
    int ls = strlen(s);
    for(int i=0;i<ls;i++) a[i]=s[i]-'a'+1; a[ls]=0;

    da(a,sa,ls+1,30);
    calheight(a,sa,ls);
    initrmq(ls+1,height);
    return 0;
}