本文主要是介绍代码随想录算法训练营第9天 | 28. 找出字符串中第一个匹配项的下标 | 459. 重复的子字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
28. 找出字符串中第一个匹配项的下标
题意
在文本串t中找到模式串s第一次出现的下标
解
kmp
int next[10005];void get_next(char *str) {int n = strlen(str);next[0] = -1;for (int i = 1, j = -1; i < n; i++) {while (j > -1 && str[i] != str[j+1]) j = next[j];if (str[i] == str[j+1]) j++;next[i] = j;}return;
}int kmp(char *t, char *s) {int i, j;int n = strlen(t), m = strlen(s);for (i = 0, j = -1; i < n; i++) {while (j > -1 && t[i] != s[j+1]) j = next[j];if (t[i] == s[j+1]) j++;if (j == m-1) return i-m+1;}return -1;
}int strStr(char* haystack, char* needle) {get_next(needle);return kmp(haystack, needle);
}
459. 重复的子字符串
题目链接
题意
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。示例 2:
输入: s = "aba"
输出: false
示例 3:输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)提示：1 <= s.length <= 104
s 由小写英文字母组成
解
官方解释如下
就是将字符串复制一遍, 然后移除第一个和最后一个字符
int next[10005];void get_next(char *str) {int n = strlen(str);next[0] = -1;memset(next, -1, sizeof(int) * 10005);for (int i = 1; i < n; i++) {int j = next[i-1];while (j != -1 && str[i] != str[j+1]) j = next[j];if (str[i] == str[j+1]) {next[i] = j + 1;} }return;
}int kmp(char *t, char *s) {int i, j;int n = strlen(t), m = strlen(s);for (i = 1, j = -1; i < n-1; i++) { // 匹配时, 从移除第一个字符while (j > -1 && t[i] != s[j+1]) j = next[j];if (t[i] == s[j+1]) {j++;if (j == m-1) return true;}}return false;
}bool repeatedSubstringPattern(char* s) {int n = strlen(s);char str[2*n+1];get_next(s);str[0] = 0;strcat(str, s);strcat(str, s);return kmp(str, s);
}
小知识点, strcat操作的dst字符串, 一定是需要以\0结尾的, 所以有str[0] = 0;
这篇关于代码随想录算法训练营第9天 | 28. 找出字符串中第一个匹配项的下标 | 459. 重复的子字符串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
