实现 strStr()采用kmp算法
实现 strStr() (implement-strstr)
实现 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() 定义相符。
最简单的
public int strStr(String haystack, String needle) {
if(haystack.length()<needle.length())return -1;
return haystack.indexOf(needle);
}
暴力搜索
java语言
//a needle in haystack
public int strStr_2(String haystack, String needle) {
int pLen = needle.length();
int sLen = haystack.length();
int i = 0;
int j = 0;
while(i<sLen&&j<pLen) {
if(haystack.charAt(i)==needle.charAt(j)) {
//①如果当前字符匹配成功（即S[i] == P[j]），则i++，j++
i++;
j++;
}else {
//②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0
i = i-j+1;
j=0;
}
}
//匹配成功，返回模式串p在文本串s中的位置，否则返回-1
if (j == pLen)
return i - j;
else
return -1;
}
c语言
int ViolentMatch(char* s, char* p)
{
int sLen = strlen(s);
int pLen = strlen(p);
int i = 0;
int j = 0;
while (i < sLen && j < pLen)
{
if (s[i] == p[j])
{
//①如果当前字符匹配成功（即S[i] == P[j]），则i++，j++
i++;
j++;
}
else
{
//②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0
i = i - j + 1;
j = 0;
}
}
//匹配成功，返回模式串p在文本串s中的位置，否则返回-1
if (j == pLen)
return i - j;
else
return -1;
}
KMP算法
next数组生成原理
next数组生成
#include<stdio.h>
//gcc kmp.c -o kmp
// $ ./kmp
void prefix_table(char pattern[],int prefix[],int n){
prefix[0]=0;
int len = 0;
int i=1;
while(i<n){
if(pattern[i]==pattern[len]){
len++;
prefix[i]=len;
i++;
}else{
if(len>0){
len = prefix[len-1];
}else{
prefix[i]=len;
i++;
}
}
}
}
int main(){
char pattern[] = "ABABCABAA";
int prefix[9];
int n=9;
prefix_table(pattern,prefix,n);
int i;
for(i=0;i<n;i++){
printf("%d\n",prefix[i]);
}
return 0;
}
输出
0
0
1
2
0
1
2
3
1
next数组后移一位，前面加上-1
next数组后移一位，前面加上-1，是为了方便匹配。
#include<stdio.h>
//gcc kmp.c -o kmp
// $ ./kmp
void prefix_table(char pattern[],int prefix[],int n){
prefix[0]=0;
int len = 0;
int i=1;
while(i<n){
if(pattern[i]==pattern[len]){
len++;
prefix[i]=len;
i++;
}else{
if(len>0){
len = prefix[len-1];
}else{
prefix[i]=len;
i++;
}
}
}
}
//next数组向前移动一位，方便kmp算法
void move_prefix_table(int prefix[],int n){
int i;
for(i=n-1;i>0;i--){
prefix[i] = prefix[i-1];
}
prefix[0] = -1;
}
int main(){
char pattern[] = "ABABCABAA";
int prefix[9];
int n=9;
prefix_table(pattern,prefix,n);
move_prefix_table(prefix,n);
int i;
for(i=0;i<n;i++){
printf("%d\n",prefix[i]);
}
return 0;
}
执行gcc kmp.c -o kmp，./kmp。
输出
-1
0
0
1
2
0
1
2
3
kmp完整代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//gcc kmp.c -o kmp
// $ ./kmp
void prefix_table(char pattern[],int prefix[],int n){
prefix[0]=0;
int len = 0;
int i=1;
while(i<n){
if(pattern[i]==pattern[len]){
len++;
prefix[i]=len;
i++;
}else{
if(len>0){
len = prefix[len-1];
}else{
prefix[i]=len;
i++;
}
}
}
}
//next数组向前移动一位，方便kmp算法
void move_prefix_table(int prefix[],int n){
int i;
for(i=n-1;i>0;i--){
prefix[i] = prefix[i-1];
}
prefix[0] = -1;
}
void kmp_search(char text[],char pattern[]){
int n = strlen(pattern);
int m = strlen(text);
int* prefix = malloc(sizeof(int) * n);
prefix_table(pattern,prefix,n);
move_prefix_table(prefix,n);
//text[i] , len(text) =m
//pattern[j], len(pattern) =n
int i = 0;
int j = 0;
while(i<m){
if(j==n-1 && text[i] == pattern[j]){
printf("Found pattern at %d\n",i-j);
j = prefix[j];
}
if(text[i]==pattern[j]){
i++;j++;
}
else{
j = prefix[j];
if(j==-1){
i++;j++;
}
}
}
}
int main(){
char pattern[] = "ABABCABAA";
char text[] = "ABABABCABAABABABAB";
kmp_search(text,pattern);
/*
int prefix[9];
int n=9;
prefix_table(pattern,prefix,n);
move_prefix_table(prefix,n);
int i;
for(i=0;i<n;i++){
printf("%d\n",prefix[i]);
}
*/
return 0;
}
输出Found pattern at 2