字符串匹配的算法（暴力算法和KMP算法）

    #include<iostream>        #include<string>        using namespace std;        int KMPfind(char* s, char* p);        void GetNext(char* p, int next[]);        int ViolentMatch(char* s, char* p);        int main()        {            char s1[] = "abcaabbaacaadaabbaa";            char s2[] = "aadaab";            cout << "In the string " << s1 << ", the string " << s2 << " is started at the "                << ViolentMatch(s1, s2);            cout << endl<<KMPfind(s1, s2)<<endl;            return 0;        }        void GetNext(char* p, int next[])        {            int pLen = strlen(p);            int i = -1; int j = 0;//i从-1开始，让不匹配的回溯到开始位置进行匹配            next[0] = -1;//            for (; j < pLen-1;)            {                if (i==-1||p[i] == p[j])                {                    ++i; ++j; next[j] = i;                }                else                    i = next[i];//i回溯到next[i]的位置            }                    }        int KMPfind(char* s, char* p)        {            int i = 0;            int j = 0;            int sLen = strlen(s);            int pLen = strlen(p);            int * next = new int[strlen(p)];            GetNext( p,  next);            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 = next[j];                }            }            delete []next;            if (j == pLen)//比较完毕而且比较了模式字符串的长度表示找到匹配字符串                return i - j;            else                return -1;        }        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算法）
