I
mplement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
找字符串出现的第一位置
-
the first solution is searching the first same char, than check whether the following str is same or not
"abcbca" "bca" "bcbca" cbca bca "bca" ca a 不对，break 从下一个字符开始找: "cbca" "bca" "bca" "bca"
class Solution { public: int strStr(string haystack, string needle) { int first=1; int i=0; if(haystack.length()<needle.length()) return -1; if(needle.length()==0) return 0; for( i=0;i<haystack.length();i++) { int j=0; if(haystack.length()-i<needle.length()-j) return -1; if(haystack[i]==needle[j]) { int t=i; int t1=i; cout<<t<<endl; for( j=0;j<needle.length();) { if(haystack[t]==needle[j]) { cout<<t<<" "<<j<<endl; t++; j++; cout<<t<<" "<<j<<endl; } else break; } if(j>=needle.length()) { cout<<j<<endl; return t1; } } } if(i>=haystack.length()) return -1; } };
- 如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；
- 如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。
-
1. S[0]为B，P[0]为A，不匹配，执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，S[1]跟P[0]匹配，相当于模式串要往右移动一位（i=1，j=0）
2. S[1]跟P[0]还是不匹配，继续执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，S[2]跟P[0]匹配（i=2，j=0），从而模式串不断的向右移动一位（不断的执行“令i = i - (j - 1)，j = 0”，i从2变到4，j一直为0）
3. 直到S[4]跟P[0]匹配成功（i=4，j=0），此时按照上面的暴力匹配算法的思路，转而执行第①条指令：“如果当前字符匹配成功（即S[i] == P[j]），则i++，j++”，可得S[i]为S[5]，P[j]为P[1]，即接下来S[5]跟P[1]匹配（i=5，j=1）
4. S[5]跟P[1]匹配成功，继续执行第①条指令：“如果当前字符匹配成功（即S[i] == P[j]），则i++，j++”，得到S[6]跟P[2]匹配（i=6，j=2），如此进行下去
5. 直到S[10]为空格字符，P[6]为字符D（i=10，j=6），因为不匹配，重新执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，相当于S[5]跟P[0]匹配（i=5，j=0）
6. 至此，我们可以看到，如果按照暴力匹配算法的思路，尽管之前文本串和模式串已经分别匹配到了S[9]、P[5]，但因为S[10]跟P[6]不匹配，所以文本串回溯到S[5]，模式串回溯到P[0]，从而让S[5]跟P[0]匹配。
而S[5]肯定跟P[0]失配。为什么呢？因为在之前第4步匹配中，我们已经得知S[5] = P[1] = B，而P[0] = A，即P[1] != P[0]，故S[5]必定不等于P[0]，所以回溯过去必然会导致失配。那有没有一种算法，让i 不往回退，只需要移动j 即可呢？
答案是肯定的。这种算法就是本文的主旨KMP算法，它利用之前已经部分匹配这个有效信息，保持i 不回溯，通过修改j 的位置，让模式串尽量地移动到有效的位置。
时间复杂度太高 m*n
class Solution {
public:
int strStr(string haystack, string needle) {
return haystack.find(needle);
}
};
we lower the time complexity to m+n by using KMP algorithm. it is a simple pattern match method. 常用于在一个文本串S内查找一个模式串P 的出现位置
向右移动4位后，S[10]跟P[2]继续匹配。为什么要向右移动4位呢，因为移动4位后，模式串中又有个“AB”可以继续跟S[8]S[9]对应着，从而不用让i 回溯。相当于在除去字符D的模式串子串中寻找相同的前缀和后缀，然后根据前缀后缀求出next 数组，最后基于next 数组进行匹配。
在D之前的所有字符串已匹配过 ABCDAB， 已匹配过的字符串尽量减少匹配。 ABCDAB中 前缀AB 和 后缀AB是相同的，后缀AB肯定和 模式串中的当前匹配位置之前的字符串匹配，因为前缀AB 与后缀AB相同， 所以直接从 C开始匹配。
怎么算移的位置，首先计算每个字符前的最长匹配前缀与后缀，从2开始。
int KmpSearch(char* s, char* p) { int i = 0; int j = 0; int sLen = strlen(s); int pLen = strlen(p); while (i < sLen && j < pLen) { //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++ if (j == -1 || s[i] == p[j]) { i++; j++; } else { //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j] //next[j]即为j所对应的next值 j = next[j]; } } if (j == pLen) return i - j; else return -1; }
- 寻找前缀后缀最长公共元素长度
比如对于字符串a来说，它之前的相同的前缀没有；aba 中 后缀a和前缀a 相同 ， 而对于字符串abab来说，后缀ab 和前缀ab相同，它有长度为2的相同前缀后缀ab（相同前缀后缀的长度为k + 1，k + 1 = 2）。
- ②求next数组
- next 数组考虑的是除当前字符外的最长相同前缀后缀，所以通过第①步骤求得各个前缀后缀的公共元素的最大长度后，只要稍作变形即可：将第①步骤中求得的值整体右移一位，然后初值赋为-1，如下表格所示：
比如对于aba来说，第3个字符a之前的字符串ab中有长度为0的相同前缀后缀，所以第3个字符a对应的next值为0；而对于abab来说，第4个字符b之前的字符串aba中有长度为1的相同前缀后缀a，所以第4个字符b对应的next值为1（相同前缀后缀的长度为k，k = 1）。
next 负责把模式串向前移动，且当第j位不匹配的时候，用第next[j]位和主串匹配，就像打了张“表”。此外，next 也可以看作有限状态自动机的状态，在已经读了多少字符的情况下，失配后，前面读的若干个字符是有用的。
- ③根据next数组进行匹配
- 匹配失配，j = next [j]，模式串向右移动的位数为：j - next[j]。换言之，当模式串的后缀pj-k pj-k+1, ..., pj-1 跟文本串si-k si-k+1, ..., si-1匹配成功，但pj 跟si匹配失败时，因为next[j] = k，相当于在不包含pj的模式串中有最大长度为k 的相同前缀后缀，即p0 p1 ...pk-1 = pj-k pj-k+1...pj-1，故令j = next[j]，从而让模式串右移j - next[j] 位，使得模式串的前缀p0 p1, ..., pk-1对应着文本串 si-k si-k+1, ..., si-1，而后让pk 跟si 继续匹配。如下图所示：
1. 字符串匹配问题
假如我们有一个模式字符串ABCDABD和一个目标字符串BBC ABCDAB ABCDABCDABDE，
我们怎样找到模式串在目标串中的匹配位置呢？
最容易想到的办法是逐个比对：源码
2. KMP算法背景
KMP算法是一种改进的字符串匹配算法，
由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为KMP算法。
KMP算法的关键是利用匹配失败后的信息，
尽量减少模式串与目标串的重复匹配次数以达到快速匹配的目的。
具体实现是利用一个事先计算好的next数组，
其中包含了模式串的前缀与后缀特征。
3. 往后跳多远
我们观察一下，看看逐个比对会包含哪些重复计算，然后想办法消除它。
考虑某个中间步骤，
BBC ABCDAB ABCDABCDABDE
ABCDABD模式串ABCDABD的子串ABCDAB都比对成功了，可是，在D处失败了。
于是下一步，我们会向后移动一个字符，继续比对，
BBC ABCDAB ABCDABCDABDE
ABCDABD可是，我们可以移动的更远一些吗？
能不能把目标串中的ABCDAB全都跳过？
BBC ABCDAB ABCDABCDABDE
ABCDABD好像不行，跳的太远了，我们得从这里开始，
BBC ABCDAB ABCDABCDABDE
ABCDABD因为ABCDAB前缀和后缀包含重叠的部分。
我们称AB为ABCDAB的前缀和后缀的最长公共序列。
跳多远=
ABCDAB长度 - 前缀和后缀的最长公共序列长度
4. next数组
前缀和后缀的最长公共序列，只和模式串有关，是模式串本身的特征。
所以，我们就可以事先算好模式串前n个字符的前缀和后缀的最长公共序列的长度，
把它们存起来，称为next数组。
对于模式串agctagcagctagct来说，
它的next数组为[0,0,0,0,1,2,3,1,2,3,4,5,6,7,4]，
即，模式串的前i+1个字符的前缀和后缀的最长公共序列的长度为next[i]。
例如：agctagcagctagct的前6个字符agctag的前缀和后缀的最长公共序列的长度为next[5]=2。
怎样计算这个数组呢？
我们可以利用next[0]~next[i]来计算next[i+1]。
假设pattern='agctagcagctagct'
a：next[0]=0，ag：pattern[1]=g，pattern[0]=a，不相等，所以next[1]=0，agc：pattern[2]=c，pattern[0]=a，不相等，所以next[2]=0，agct：pattern[3]=t，pattern[0]=a，不相等，所以next[3]=0，agcta：pattern[4]=a，pattern[0]=a，相等，所以next[4]=1，agctag：pattern[5]=g，pattern[1]=g，相等，所以next[5]=2，agctagc：pattern[6]=c，pattern[2]=c，相等，所以next[6]=3，
……agctagcagctagc：pattern[13]=c，pattern[6]=c，相等，所以next[13]=7
5. 次长公共序列
难点来了。agctagcagctagct：pattern[14]=t，pattern[7]=a，不相等。
怎么办？于是next[14]=0吗？
很显然不行，因为agct是前缀和后缀的最长共同序列，next[14]=4。
寻找agct基于以下考虑，
如图，橙色的A表示已经确定的最长公共序列，绿色的T将要与开头的A后面的元素进行比较。
如果比对失败，我们需要寻找次长公共序列B，然后T再与开头的B后面元素进行比对。
我们看到，三幅图中，橙色块都是相等的，
如果存在次长公共序列，第二幅图表明，橙色块必然同时以B开头且以B结尾。
即，如第三幅图所示，
这表明，T位置的次长公共序列长度，就是橙色块的最长公共序列长度。
因此，计算agctagcagctagc的次长公共序列，就要计算B=agctagc的最长公共序列，
而这个已经计算过了，next[6]=3，得到agc。
然后与agc后面的元素t进行比对，相等，next[14]=4。
作者：何幻
链接：http://www.jianshu.com/p/6c53d06d23cc
來源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。