模式匹配算法(KMP+字典树+AC自动机)

KMP算法:1对1模式匹配

参考地址

1对1的意思是给定一个单词看是否在某个文章(长字符串)中出现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 计算next数组
public static int[] getNext(String ps) {
char[] p = ps.toCharArray();
int[] next = new int[p.length];
next[0] = -1;
int j = 0;
int k = -1;

while (j < p.length - 1) {
if (k == -1 || p[j] == p[k]) {
if (p[++j] == p[++k]) { // 当两个字符相等时要跳过
next[j] = next[k];
} else {
next[j] = k;
}
} else {
k = next[k];
}
}
return next;
}
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
//完整代码
public static int KMP(String ts, String ps) {
char[] t = ts.toCharArray();
char[] p = ps.toCharArray();
int i = 0; // 主串的位置
int j = 0; // 模式串的位置
int[] next = getNext(ps);
while (i < t.length && j < p.length) {
if (j == -1 || t[i] == p[j]) { // 当j为-1时,要移动的是i,当然j也要归0
i++;
j++;
} else {

// i不需要回溯了
// i = i - j + 1;

j = next[j]; // j回到指定位置
}
}

if (j == p.length) {
return i - j;
} else {
return -1;
}
}

字典树:1对多模式匹配

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
#include <iostream>
#include <unistd.h>
#include <pthread.h>
#include <string>
using namespace std;

class TrieNode{ // 字典树节点
public:
int num;// 有多少单词通过这个节点,即由根至该节点组成的字符串模式出现的次数
// TrieNode** son;// 所有的儿子节点
TrieNode* son[26];
bool isEnd;// 是不是最后一个节点
char val;// 节点的值

TrieNode(){
num = 1;
// son = new TrieNode*[26];
isEnd = false;
}
~TrieNode(){
// for(int i = 0; i < 26; i++){
// delete son[i];
// }
// delete son;
}
}root;

// 建立字典树
void insert(string str){ // 在字典树中插入一个单词
TrieNode* node = &root;
for (int i = 0, len = str.length(); i < len; i++){
int pos = str[i] - 'a';
if (node->son[pos] == NULL) //如果当前节点的儿子节点中没有该字符,则构建一个TrieNode并复值该字符
{
node->son[pos] = new TrieNode;
node->son[pos]->val = str[i];
}
else //如果已经存在,则将由根至该儿子节点组成的字符串模式出现的次数+1
{
node->son[pos]->num++;
}
node = node->son[pos];
}
node->isEnd = true;
}

// 在字典树中查找一个完全匹配的单词.
bool search(string str){
TrieNode* node = &root;
for(int i = 0,len = str.length(); i < len; i++){
int pos = str[i] - 'a';
if(node->son[pos] != NULL){
node = node->son[pos];
}else{
return false;
}
}
//走到这一步,表明可能完全匹配,也可能部分匹配,如果最后一个字符节点为末端节点,则是完全匹配,否则是部分匹配
return node->isEnd;
}

int main(){
return 0;
}

以动态分配为实现的带增删改查的字典树模版.

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
//一个以链表实现带删除功能允许重复字符串的字典树
#include <stdio.h>
#include <string.h>
#include <stdlib.h>


int charmapping[256]; //字符映射数组,charmapping[i]=x表示ascii码为i的字符对应于treenode中的next[x]
void init_charmapping(){
for(int i='a';i<='z';i++){ //我的这个字典树现在只允许输入小写字符组成的字符串,然而由于有charmapping的存在,增加新字符添加映射并且增大maxn就好,很方便.
charmapping[i]=i-'a';
}
}

const int maxn=26; //这里假设字符串中只出现26个小写字母
const int maxm=100000;
struct treenode{
int count; //标志此节点所表示字符串在所有字符串中以前缀形式出现的总次数
treenode* next[maxn];
}head;

void init_trie(){
head.count=1; //初始化为1包括空串并且避免树头被删
for(int i=0;i<maxn;i++) head.next[i]=NULL;
}

treenode* createnew(){ //申请一个新结点并初始化它
treenode* newnode;
newnode=(treenode*)malloc(sizeof(treenode));
newnode->count=0;
for(int i=0;i<maxn;i++) newnode->next[i]=NULL;
return newnode;
}

void update(char* s,int num){ //向字典树添加num个字符串s
int k=0,temp;
treenode* t=&head;
while(s[k]){
t->count+=num;
temp=charmapping[s[k]];
if(!t->next[temp]) t->next[temp]=createnew();
t=t->next[temp];
k++;
}
t->count+=num;
}

bool search(char* s,int num){ //查找字典树中是否已经存在num个字符串s
int k=0,temp;
treenode* t=&head;
while(s[k]){
temp=charmapping[s[k]];
if(!t->next[temp]||t->next[temp]->count<num) return false; //根本不存在字符串s或者存在的数目小于num直接失败
t=t->next[temp];
k++;
}
int snum=t->count;
for(int i=0;i<maxn;i++) if(t->next[i]) snum-=t->next[i]->count; //这里是核心!!!结点t代表的字符串出现的次数就是总次数减去所有子节点次数和
if(snum>=num) return true; //如果字符串s的数目snum大于等于num
return false;
}

void erase(char* s,int num){ //删除字典树中的num个字符串s并释放无用结点,删除前一定要先search是否存在
int k=0,temp;
treenode* t=&head;
treenode* t1; //t1后面的结点都是删除后需要被释放的
head.count-=num;
while(s[k]){
temp=charmapping[s[k]];
t->next[temp]->count-=num;
if(t->next[temp]->count==0){
t1=t->next[temp];
t->next[temp]=NULL;
k++;
break;
}
t=t->next[temp];
k++;
}
while(s[k]){ //释放无用结点
temp=charmapping[s[k]];
t=t1->next[temp];
free(t1);
t1=t;
k++;
}
free(t1);
}

char temp[1000];
void printall(treenode* tnode,int pos){ //递归打印字典树咯,打出了就是字典序升序的
int count=tnode->count;
for(int i=0;i<maxn;i++) if(tnode->next[i]) count-=tnode->next[i]->count;
for(int i=0;i<count;i++) printf("\"%s\"\n",temp);
for(int i='a';i<='z';i++){
if(tnode->next[charmapping[i]]){
temp[pos]=i;
temp[++pos]='\0';
printall(tnode->next[charmapping[i]],pos);
temp[--pos]='\0';
}
}
}

int main(){
init_charmapping(); //初始化映射
init_trie(); //初始化字典树
char x[1000];
char order; //命令
int num; //数目
printf("q:查询\nu:插入\nd:删除\np:打印字典树\ne:退出\n");
while(1){
printf("请输入命令:");
fflush(stdin);
scanf("%c",&order);
if(order=='q'){
printf("请输入要查找的字符串与数目:");
scanf("%s%d",&x,&num);
if(search(x,num)) printf("匹配成功。\n\n");
else printf("匹配失败,不存在%d个\"%s\"\n\n",num,x);
}
else if(order=='u'){
printf("请输入要插入的字符串与数目:");
scanf("%s%d",&x,&num);
update(x,num);
printf("%d个\"%s\"已加入字典树。\n\n",num,x);
}
else if(order=='d'){
printf("请输入要删除的字符串与数目:");
scanf("%s%d",&x,&num);
if(!search(x,num)){
printf("树中无%d个字符串\"%s\"请重新键入命令!\n\n",num,x);
continue;
}
erase(x,num);
printf("%d个\"%s\"已从字典树中删除。\n\n",num,x);
}
else if(order=='p'){
printf("当前字典树内有如下字符串:\n");
temp[0]='\0';
printall(&head,0);
}
else if(order=='e'){
printf("退出ing....\n");
break;
}
else printf("无效命令,请重新输入!\n命令q:查询是否存在字符串\n命令u:往字典树加入字符串\n命令d:删除某个字符串\n命令p:按字典序升序输出字典树\n命令e:退出程序\n\n");
}
return 0;
}

AC自动机:多对多模式匹配

多对多的意思是指给定多个单词,查看所有单词在给定文章中的出现的次数

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
struct node
{
int son[26];
int fail;
int count;
void init()
{
memset(son, -1, sizeof(son));
fail = 0;
count = 0;
}
}s[500005];

void insert()
{
int len = strlen(str);
int i, j, ind;
for(i = ind = 0; i < len; i++)
{
j = str[i] - 'a';
if(s[ind].son[j] == -1)
{
s[sind].init();
s[ind].son[j] = sind++;
}
ind = s[ind].son[j];
}
s[ind].count++;
}


void make_fail()
{
qin = qout = 0;
int i, ind, ind_f;
for(i = 0; i < 26; i++) {
if(s[0].son[i] != -1) {
q[qin++] = s[0].son[i];
}
}
while(qin != qout) {
ind = q[qout++];
for(i = 0; i < 26; i++) { //找之后的子节点
if(s[ind].son[i] != -1) {
q[qin++] = s[ind].son[i];
ind_f = s[ind].fail;
while(ind_f > 0 && s[ind_f].son[i] == -1)
ind_f = s[ind_f].fail;
if(s[ind_f].son[i] != -1)
ind_f = s[ind_f].son[i];
s[s[ind].son[i]].fail = ind_f;//子节点的fail根据父节点fail指针的搞定
}
}
}
}

int fd() {
int ct = 0;
int di, i, ind, p;
int len = strlen(des);//这个是文章
for(di = ind = 0; di < len; di++) {
i = des[di] - 'a';
while(ind > 0 && s[ind].next[i] == -1)
ind = s[ind].fail;

if(s[ind].next[i] != -1) {//等于-1的时候就已经是找打了根节点。
ind = s[ind].next[i];
p = ind;
while(p > 0 && s[p].count != -1) {//这里是精髓。在找过某个有标记的节点的时候
ct += s[p].count; //答案 //会把该位的标记标记为-1,在下次经过有-1
s[p].count = -1; //标记的时候,说明之后的都被计算过,不用
p = s[p].fail; //再重复计算了。
}
}
}
return ct;
}