KMP算法
今天正好复习数据结构，结合之前在代码随想录上对kmp算法的描述，重新反刍一下kmp算法
4.1串的定义和实现
字符串简称串，串是由零个或多个字符组成的有限序列。一般记为 S='a1a2...an'
串中字符的个数n称为串的长度。n=0时的空串称为空串
串中的任意多个连续的字符组成的子序列称为该串的子串，包含子串的串称为主串。由一个或者多个空格组成的串称为空格串。
4.2 串的模式匹配
子串的定位操作通常称为串的模式匹配，它求的是子串（模式串）在主串中的位置。
4.2.1 简单的模式匹配算法
算法思想：从S的第一个字符起，与模式T的第一个字符比较，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起，重新和模式的字符串比较。以此类推，直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则匹配成功。
该算法的最坏时间复杂度为O(nm),n和m分别为主串和模式串的长度
4.2.2 串的模式匹配算法——KMP算法
前缀、后缀和部分匹配值。前缀指的是除了最后一个字符以外，字符串所有的头部子串
后缀指的是除了第一个字符外，字符串的所有尾部子串
部分匹配值则为字符串前缀和后缀的最长相等前后缀长度。
按照下面的公式计算出子串需要向后移动的位数：
移动位数=已匹配的字符数-对应的部分匹配值
这样主串就不用回溯，该算法的时间复杂度为O(m+n)
leetcode28题：实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2
示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1
说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
KMP算法可以运行的源代码如下图所示
#include <bits/stdc++.h>using namespace std;void getNext(int *next,string s)
{int j=0; next[0]=0;for(int i=1;i<s.size();i++){while(j>0&&s[i]!=s[j])j=next[j-1];if(s[i]==s[j])j++;next[i]=j; }
}
int kmp(string haystack,string needle)
{if(needle.size()==0) return 0;int next[needle.size()];getNext(next,needle);int j=0;for(int i=0;i<haystack.size();i++){while(j>0&&haystack[i]!=needle[j])j=next[j-1];if(haystack[i]==needle[j])j++;if(j==needle.size())return (i-needle.size()+1);}return -1;
}
int main()
{ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0);string s1,s2;cin>>s1>>s2;cout<<kmp(s1,s2)<<endl; return 0;
}注意KMP算法还可以编译原理中的状态机知识来理解呢
leetcode459题 重复的子字符串
#include <bits/stdc++.h>using namespace std;void getNext(int* next,string s)
{next[0]=0;int j=0;for(int i=1;i<s.size();i++){while(j>0&&s[i]!=s[j]) j=next[j-1];if(s[i]==s[j]) j++;next[i]=j;}
}
bool check(string s)
{if(s.size()==0)return false;int next[s.size()];getNext(next,s);int len=s.size();//则说明数组的长度正好可以被 (数组长度-最长相等前后缀的长度)整除，说明该字符串有重复的子字符串 if(next[len-1]!=0&&len%(len-(next[len-1]))==0)return true;return false;
}
int main()
{ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0);string s;cin>>s;if(check(s)) cout<<"yes"<<endl;else cout<<"no"<<endl;return 0;
}
