面试算法题之字符串，字符串哈希、KMP算法
找出字符串中第一个匹配项的下标
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
裁剪字符串
思路就是直接截取目标字符串长度的子串，再与目标字符串进行对比，相同则返回字符开始下标，若遍历完字符串仍未找到目标字符串则返回-1。
class Solution {
public:
int strStr(string haystack, string needle) {
for(int i=0;i<haystack.length();i++) {
if(haystack.substr(i, needle.length()) == needle) {
return i;
}
}
return -1;
}
};时间复杂度为 O(n)，空间复杂度：O(1)
KMP 算法（Knuth Morris Pratt）
KMP 算法是一种用于在字符串中查找子串的高效算法。算法的核心思想是利用已经匹配过的信息来避免重复的比较。
在传统的字符串匹配算法中，当遇到不匹配的情况时，通常会将模式串向后移动一位，然后重新开始比较。而 KMP 算法通过预先计算模式串中每个位置的最长公共前缀和最长公共后缀的长度，从而可以在不匹配的情况下直接将模式串向后移动到合适的位置，而不需要重新开始比较。
具体来说，KMP 算法可以分为两个阶段。第一阶段是构建 next 数组，即计算模式串中每个位置的最长公共前缀和最长公共后缀的长度。第二阶段是利用 next 数组进行匹配，即在匹配过程中利用已有的信息来避免重复的比较。
class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.length(), m = needle.length();
if(m==0) return 0;
vector<int> p(m);
for(int i=1, j=0;i<m;i++) {
while(j > 0 && needle[i] != needle[j]) {
j = p[j-1];
}
if(needle[i] == needle[j]) {
j++;
}
p[i] = j;
}
for(int i=0,j=0;i<n;i++) {
while(j>0 && haystack[i] != needle[j]) {
j=p[j-1];
}
if(haystack[i] == needle[j]) {
j++;
}
if(j==m) {
return i-m+1;
}
}
return -1;
}
};KMP 算法的时间复杂度为 O(m+n)，空间复杂度：O(n)，其中 m 为模式串的长度，n 为文本串的长度。
重复的子字符串
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
枚举思路
由题意我们可以得知，字符串长度 n 一定是子串长度 m 的倍数，并且子串 s`一定是该字符串 s 的前缀。
由此，有s[i]=s[i−m]s[i]=s[i-m]s[i]=s[i−m]。我们可以由这些规则去解题，遍历字符串，然后对比s[i]==s[i−m]s[i]==s[i-m]s[i]==s[i−m]，直到完全匹配上。
小优化：遍历字符串的一半长度就好了，超过一半还没有匹配上就肯定不符合题意了。如果 n%i!=0 肯定不是符合条件的解，遍历的时候可以
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int n = s.length();
for(int i=1;i*2<=n; i++) {
if(n % i == 0) {
bool match = true;
for(int j=i; j<n;j++) {
if(s[j] != s[j-i]) {
match = false;
break;
}
}
if(match) {
return true;
}
}
}
return false;
}
};时间复杂度：O(n2)O(n^2)O(n2)，空间复杂度：O(1)，其中 n 是字符串 s 的长度。
转换思路——匹配字符串
如果字符串是由它的一个子串重复多次构成的，那么字符串本身就是一个重复的子串，如此我们可以再拼接一个字符串 s，并移除第一个和最后一个字符。如果字符串 s 是该字符串的子串，那么 s 就符合题目要求的。
从下标 1 开始查找 s 字符串，如果匹配上的下标不是拼接处下标，即表示该字符串符合题意。
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int n = (s+s).find(s, 1) ;
return n != s.length();
}
};此题目如此变换后，也可以使用 KMP 算法求解。
最短回文串
给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
字符串哈希
从左往右遍历，计算当前这个子串 s[1,i] 的正向 p 进制的哈希值 l 和反向 p 进制表示哈希值 r，如果两者相同，说明当前子串是个回文串。
class Solution {
public:
typedef unsigned long long ULL;
string shortestPalindrome(string s) {
int n = s.length(), pos;
if(n==0) return "";
int p = 131;
ULL l = 0, r = 0, q = 1;
for(int i=0;i<n;i++) {
l = l*p + s[i];
r = r+s[i]*q;
q*=p;
if(l == r)
pos = i;
}
string t = s.substr(pos+1);
reverse(t.begin(), t.end());
return t+s;
}
};- 时间复杂度：O(n)，空间复杂度：O(1)。