【牛客带你学编程C++方向】项目练习第2期（截止2.27）

/*若主串长度为N，子串长度为M，暴力求解时间复杂度为O(M x N)。 KMP 算法时间复杂度O(M)+O(N)。算法最主要的就是子串的next数组的构造了。 首先生成子串的next_arr数组，这个数组长度与子串长度一致。数组中第i个 元素next_arr[i]的含义是B[i]之前的字符串B[0...i-1]中，必须以B[i-1]结尾 的后缀子串（不能包含B[0]）与必须以B[0]开头的前缀子串（不能包含B[i-1]） 最大匹配长度是多少，这个长度就是next_arr[i]的值。子串用处：当到第i个 元素与主串不匹配的时候，可以不一定要从子串头和主串初始匹配时的下一个 元素做起点开始匹配。因为next_arr数组记录了子串第i个元素之前的子串特性。 若子串在B[i]处于主串A[j]处不匹配，则j位置不变，下次从B[next_arr[i]]处 继续和A[j]相比。*/ #include<iostream> #include<string> using namespace std; //求子串next数组 int* getnext_arr(string B) { int len = B.length(); int* next = new int[len]; next[0] = -1; if(len==1)   return next;   next[1] = 0;   int pos = 2;   int cn = 0;   while(pos < len)   {   if(B[pos-1] == B[cn]) next[pos++] = ++cn; else if(cn > 0) cn = next[cn]; else next[pos++] = 0; } return next; } //匹配，若能匹配，返回主串匹配起始的下标，若不能则返回-1 int getIndex(string A, string B) { if(A == "" || B == "" || B.length() < 1 || A.length() < B.length()) return -1; int Ai = 0, Bi=0; int *next = new int[B.length()]; next = getnext_arr(B); while(Ai < A.length() && Bi < B.length()) { if(A[Ai] == B[Bi]) { Ai++; Bi++; } else if(next[Bi] == -1) { Ai++; } else { Bi = next[Bi]; } } return Bi == B.length() ? Ai - Bi : -1; } int main() { string A,B; while(cin>> A >> B) { cout<<getIndex(A,B) <<endl; } return 0; }

#include<iostream> using namespace std; int main() {     char A[] = "ababcabcacbab";     char B[] = "abcac";     int n = strlen(B);     int i, r,m;     for (i = 0; A[i] != '\0'; i++) {         for (m=i,r = 0; r < n; m++,r++) {             if (A[m] != B[r])break;         }         if (A[m - 1] == B[r - 1]&&r==n) {             cout<<"找到了,在A的第"<<i + 1<<"个到"<<i + n<<"个";             break;         }     }     if (A[i] == '\0')cout << "查无此字符串";     return 0; }

就是KMP呀，但是我现在还没学会呀呀呀，大佬们，next数组，这么用最少的时间复杂度来写？

#include<stdio.h> #include<stdlib.h> #include<string.h> int *GetNext(char *match) {     int i;     i = 1;     int *pNext = NULL;     pNext = (int*)malloc(sizeof(int)*strlen(match));     pNext[0] = 0;     int j;     j = i-1;     while(i < strlen(match))     {         if(match[i] == match[pNext[j]])         {             pNext[i] = pNext[j]+1;             i++;             j = i-1;         }         else if(pNext[j] == 0)         {             pNext[i] = 0;             i++;             j = i-1;         }         else         {             j = pNext[j]-1;         }     }     return pNext; } int KMP(char *src,char *match) {     if(src == NULL || match == NULL)return -1;     int *pNext = NULL;     //获得Next数组     pNext = GetNext(match);     //查找     int i;     int j;     i = 0;     j = 0;     while(i < strlen(src)&& j<strlen(match))     {         if(src[i] == match[j])         {             i++;             j++;         }         else         {             //不想等 且匹配串已经回到开始位置仍不相等 主串向后移动             if(j == 0)             {                 i++;             }             //匹配串向前移动             else             {                 j = pNext[j-1];             }         }     }     //匹配串已经走完  结束     if(j == strlen(match))     {         return i-j;     }     return -1; } int main() {     char *src = "ahfhawoerqhewqlknxcabcabcdabcabcfjfesaruwqou";     char *match = "abcahseifysfryewbcdabcabcf";     int n;     n = KMP(src,match);     printf("%d\n",n);     return 0; }

算不算详解

#include<stdio.h> //计算next[]数组 ，长度与子串相同  void cal_next(char *str,int *next,int len) {     next[0]=-1;//-1表示不存在前后缀相同     int k=-1;     for(int q=1;q<=len-1;q++)     {         while(k>-1&&str[k+1]!=str[q])         {             k=next[k];         }         if(str[k+1]==str[q])         {             k=k+1;         }          next[q]=k;     }  } int KMP(char *str,int slen,char *ptr,int plen) {     int *next=new int[plen];     cal_next(ptr,next,plen);     int k=-1;     for(int i=0;i<slen;i++)     {         while(k>-1&&ptr[k+1]!=str[i])         {             k=next[k];         }         if(ptr[k+1]==str[i])         {             k=k+1;         }         if(k==plen-1)//找到该子串          {             return i-plen+1;//返回对应子串在主串的第一个下标          }     }     return -1; } int main() {     char *str="ababcabcacbab";     char *ptr="abcac";     int a=KMP(str,13,ptr,5);     printf("%d\n",a);     return 0;   }

#include <iostream> #include <string> using namespace std; int b_force_match(string str, string ptr) {     int i, j, temc;     int tlen = ptr.length();     int plen = str.length();     for (i = 0, j = 0; i <= plen - tlen; i++)     {         temc = i;         j = 0;         while (str[temc] == ptr[j] && j < tlen)         {             temc++;             j++;         }         if (j == tlen)             return i;     }     return -1; } void clnext(string str, int *next) {     int len=str.length();     next[0] = -1;     int k = -1;     for (int q = 1; q < len; q++)     {         while (k > -1 && str[k + 1] != str[q])             k = next[k];//回溯         if (str[k + 1] == str[q])            k++;         next[q] = k;     } } int KMP(string str,string ptr) {     int slen=str.length();     int plen=ptr.length();     int *next = new int[plen];     clnext(ptr, next);     int k = -1;     for (int i = 0; i < slen; i++)     {         while (k >-1&& ptr[k + 1] != str[i])             k = next[k];         if (ptr[k + 1] == str[i])             k = k + 1;         if (k == plen-1)         {             delete next;             return i-plen+1;         }     }     delete next;     return -1; } int main() {     string str = "ahraaahahafafderqhgadgdfghadfhnmym,,aryzkiababaabaftyacfabaou";     string ptr = "ababaabaf";     cout << "patternmatch" << endl;     cout << "b_force:" << endl;     cout << b_force_match(str, ptr) << endl;     cout<<"KMP:"<<endl;     cout << KMP(str, ptr) << endl;     return 0; }