字符串匹配(3)kmp
字符串 匹配 KMP
2023-09-27 14:26:25 时间
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 10000
#define DEFAULT_LEN 40
char s[MAX_N + 5], t[MAX_N + 5];
#define TEST(func) { \
char temp_s[MAX_N + 5]; \
sprintf(temp_s, "%s(\"%s\", \"%s\") = %3d\n", #func, s, t, func(s, t)); \
int n = DEFAULT_LEN - strlen(temp_s); \
while (n--) printf(" "); \
printf("%s", temp_s); \
}
int brute_one_match(const char* s, const char* t) {
for (int j = 0; t[j]; j++) {
if (s[j] == t[j]) continue;
return 0;
}
return 1;
}
int brute_force(const char* s, const char* t) {
for (int i = 0; s[i]; i++) {
if (brute_one_match(s + i, t)) return i;
}
return -1;
}
int quick_mod(int a, int b, int c) {
int ans = 1, temp = a;
while (b) {
if (b & 1) ans = ans * temp % c;
temp = temp * temp % c;
b >>= 1;
}
return ans;
}
int hash_match(const char* s, const char* t) {
int len = strlen(t), base = 31, P = 9973, nbase = quick_mod(base, len, P);
int h = 0, th = 0;
for (int i = 0; t[i]; i++) th = (th * base + t[i]) % P;
for (int i = 0; s[i]; i++) {
h = (h * base + s[i]) % P;
if (i >= len) h = (h - (s[i - len] * nbase % P) + P) % P;
if (i + 1 < len) continue;
if (h != th) continue;
if (brute_one_match(s + i - len + 1, t)) return i - len + 1;
}
return -1;
}
int* getNext(const char* t, int* n) {
*n = strlen(t);
int* next = (int*)malloc(sizeof(int) * (*n));
next[0] = -1;
for (int i = 1, j = -1; t[i]; i++) {
while (j != -1 && t[j + 1] != t[i]) j = next[j];
if (t[j + 1] == t[i]) j += 1;
next[i] = j;
}
free(next);
return next;
}
int kmp(const char* s, const char* t) {
int len;
int* next = getNext(t, &len);
for (int i = 0, j = -1; s[i]; i++) {
while (j != -1 && t[j + 1] != s[i]) j = next[j];
if (t[j + 1] == s[i]) j += 1;
if (t[j + 1] == '\0') return i - len + 1;
}
return -1;
}
int test_func(const char* s, const char* t) {
return -1;
}
int main() {
while (~scanf("%s%s", s, t)) {
TEST(brute_force);
TEST(test_func);
TEST(hash_match);
TEST(kmp);
}
return 0;
}
相关文章
- 字符串匹配算法——KMP算法
- 括号匹配问题:判断一个字符串是否为有效的括号匹配
- AC自动机:在一篇文章paper字符串中,搜索查找一批matches字符串,看看有哪些字符串能匹配上
- KMP算法预备知识:字符串match的每一个位置i之前的字符串,前缀与后缀匹配的最大长度是多少
- C#,字符串匹配(模式搜索)KMP算法的源代码与数据可视化
- 正则表达式总结,正则表达式匹配不包含某个字符串
- js 正则: 匹配不含有某段字符串的行
- 蓝桥杯《算法很美》第5章:字符串与字符串匹配(暴力匹配和KMP)
- iOS截取特定的字符串(正则匹配)
- Java实现字符串的匹配
- 从hadoop 要删除字符串匹配指定的任务
- 字符串匹配的KMP算法——Python实现
- [LeetCode] 1221. Split a String in Balanced Strings 分割平衡字符串
- [LeetCode] Valid Palindrome 验证回文字符串
- 【漏洞分析】Mozilla Firefox 字符串替换堆破坏漏洞(CVE-2013-0750)
- 【codevs1404】字符串匹配 KMP
- Java-字符串