KMP字符串匹配 · CSGrandeur/s |
您所在的位置：网站首页 › ac自动机last优化 › KMP字符串匹配 · CSGrandeur/s |
KMP字符串匹配 · CSGrandeur/s
|
KMP模式匹配
介绍
KMP算法是一种优化过的字符串匹配算法,它能在线性的时间内判定出字符串A(模式串)是否为字符串B(主串)的子串并求出对应的位置.其优化原理就在于每次匹配失败后在回溯时能通过next数组来减少字符的重复比较(next数组中保存了模式串的局部匹配信息),时间复杂度为O(n+m)(朴素解法为O(n*m)) 对比: 朴素解法是枚举主串的每个点来挨个提取子串做比较
而kmp算法则会直接使用next数组来跳过重复的比较步骤,这里我们先来介绍下next数组
next数组意义: 对于字符串 S 的前 i 个字符构成的子串所具有的最长前后缀长度 用公式表示为 next[i]=max{j},其中j next[1] = 1; for (int i = 2, j = 0; i 0 && a[i-1] != a[j]) j = next[j]; if (a[i-1] == a[j]) j++; next[i] = j; } KMP算法的一共就分两步: 在正式匹配前对模式串做"自匹配"(求出需要的next数组) 对主串和模式串进行匹配前一步已经做成,后一步由于字符串的"自匹配"和实际的匹配原理一致(自匹配就是一个字符串同时为主串和模式串),所以这两个步骤的模板大体一致,都是在交替地尝试拓展和查找新的匹配起点 for (int i = 2, j = 0; i 0 &&(j==n|| b[i - 1] != a[j])) j = next[j]; //求出字符串B中以b[i-1]结尾地子串和字符串A前缀的最大匹配长度 if (b[i - 1] == a[j]) j++; //if (j == n) ;匹配成功 } 补充:若把trie字典和kmp相结合,还可以得到AC自动机算法(KMP算法适用于单模式串的匹配，而AC自动机适合多模式串的匹配) AC自动机的步骤如下: 把多个模式串放入trie字典树中 按照bfs的写法求"fail数组"(fail数组与next数组含义类似,它表示在某一位置匹配失败时需要跳转到的新位置) 模式匹配可以说kmp是AC自动机的特殊情况 实践kmp适用于解决子串查找,前后缀匹配和求解公共子串等问题,下面是对应的具体应用 一.查找子串Wow! Such Doge! (hdu-4847) 题目大意查找输入文章中单词doge(大小写不敏感)的出现次数 思路由于单词doge各个字母都不同,所以其next数组中所有元素恒为0,可以直接令单词doge和输入字符串做匹配,统计匹配成功的次数 #include #include #include #include #include #include using namespace std; //打表列出"doge"的所有形式 char b[64005],a[20][10] = { "doge","Doge","dOge","doGe", "dogE", "DOge", "DOGe", "DOGE","DOgE","DoGE","DoGe","DogE","dOGE","dOgE","dOGe","doGE" }; int kmp(char a[], char b[]) { int N = 0; //两字符串可直接进行匹配 for (int i = 1, j = 0; i 0 && (j == 4 || b[i - 1] != a[j])) j = 0; if (b[i - 1] == a[j]) j++; if (j == 4) N++; } return N; } int main() { std::ios::sync_with_stdio(0); int N = 0; while (cin>>b) { //遍历"doge"的所有形式 for (int i = 0; i < 16; i++) { //求出每个"doge"在输入字符串中的出现次数 N += kmp(a[i], b); } } //输出总和 cout #include #include #include #include #include #include using namespace std; char b[1000005], a[1000005]; int n, m, x,nex[1000005]; int main() { cin >> x; cin >> b; cout > a; n = strlen(a); nex[1] = 0; int N ; //字符串a的自匹配 for (int i = 2, j = 0; i 0 && a[i-1] != a[j]) j = nex[j]; if (a[i-1] == a[j]) j++; nex[i] = j; } //匹配字符串a与b for (int i = max(1,m-n+1), j = 0; i 0 && (j == n || b[i-1] != a[j])) j = nex[j]; if (b[i-1] == a[j]) j++; //最后所得的N值即为前后缀最大匹配长度 N = j; } //输出非字符串a的"重复"部分,并将字符串a,b进行去"重复"的合并 for (int i = N; i < n; i++) cout #include #include #include #include #include #include using namespace std; char a[205],b[4005][205]; int N,M, t,n, nex[1005],len[4005],k,l,r; int kmp(int z,int s) { int m = 0; for (int i = 1, j = 0; i 0 && (j+s == n || b[z][i - 1] != a[j + s])) j = nex[j]; if (b[z][i-1] == a[j+s]) j++; //求能匹配上的最长前缀 m = max(m, j); } return m; } int fas(int s) { nex[1] = 0; //模式串自匹配 for (int i = 2, j = 0; i+s 0 && a[i-1+s] != a[j+s]) j = nex[j]; if (a[i-1+s] == a[j + s])j++; nex[i] = j; } int m = 200; for (int i = 0; i < t; i++) { //取最长前缀长度中最小的一个 m = min(m, kmp(i, s)); } return m; } //字典序比较 bool check(int a1, int a2) { for (int i = 0; i < M; i++) if (a[i + a1] > a[i + a2]) return 0; else if (a[i + a1] < a[i + a2]) return 1; return 0; } int main() { while (cin >> t) { if (!t)break; M = r = 0; t--; cin >> a; n = strlen(a); for (int i = 0; i < t; i++){ //用len[]数组保存字符串长度 cin >> b[i]; len[i] = strlen(b[i]); } //枚举由字符串a生成的模式串 for (int i = 0; i < n; i++) { int t = fas(i); if (t> M||(t == M && check(i, l))){ //l,r表示最长公共子串的左右端点 M = t; l = i; r = i + M; } } //借助r来判断最长公共子串是否存在 if (r) for (int i = l; i < r; i++) cout |
【本文地址】
今日新闻 |
推荐新闻 |