亚洲久悠悠AV在线,亚洲午夜精品在线观看,又黄又紧又湿的A视频

對于字符串匹配，如用一個長度為m的模式串去匹配一個長度為n的主串，我們可以使用暴力法（BF，Brute Force），其時間復雜度為O(m*n)。

字符串匹配kmp算法的時間復雜度只需要O(m+n)。

使用變量 i, j 表示主串s[]和模式串t[]的下標，第一輪匹配：

kmp算法認為，i 可以不回退（BF要求退回到主串的第2個位置（第幾輪就是第幾個位置）），而 j 可以回退到第2個位置，即 j=2（BF要求退回到每1個字符的位置）。

即使使用暴力破解，幾輪迭代后，也會迭代匹配到此位置，所以上述 i，j 的回退不影響整體結果的正確性。

模式串此時回退為什么是2呢？

看下面已匹配的公共部分：

主串以不匹配的位置為基準，考慮前面的字符abaab，有后綴ab與模式串abaabe最前面的字符前綴ab相等。

也就是模式串本身abaab，有最大后綴部分ab與最大前綴ab相等，相等字符的長度為2。

從上圖可見，假設一個字符串長度為n，其最大前綴和后綴相等的字符數量不會超過n/2，例如：

abcdabcd，長度為8，8/2=4，其最大前綴和后綴相等的字符串abcd最大可能的長度為4。

如何暴力計算下面字符的最大前綴和后綴字符串的長度L呢？

abcdaabbcdeabcd，長度n為15，其L不會超過n/2=7，暴力匹配的思路可以描述為：

前1個字符與后1個字符是否相等？

前2個字符與后2個字符是否相等？

前3個字符與后3個字符是否相等？

……

前n/2個字符與后n/2個字符是否相等？

暴力匹配的思路也可以描述為：

前n/2=7個字符與后n/2=7個字符是否相等？

abcdaabbcdeabcd

前n/2-1=6個字符與后n/2-1=6個字符是否相等？

abcdaabbcdeabcd

前n/2-2=5個字符與后n/2-2=5個字符是否相等？

abcdaabbcdeabcd

前n/2-3=4個字符與后n/2-3=4個字符是否相等？

abcdaabbcdeabcd

此時相等，則L為4。

對于模式串abaabe，如何計算各個子串對應的最大前綴與后綴字符串數量（j回退到的位置）？

abaab	2
abaa	1
aba	1
ab	0
a	-1

圖示：

對應代碼：

int *getNextArray(char t[]) // 動態規劃
{
    int n = strlen(t);
    int *next = (int*)malloc(sizeof(int)*n);
    next[0] = -1;
    next[1] = 0;
    int k;
    for (int j = 2; j < n; j++) {
        k=next[j-1];            // 先假設
        while (k!=-1) {
            if (t[j - 1] == t[k]) {
                next[j] = k + 1;
                break;
            }else
                k = next[k];    // 回退
            next[j] = 0;  //當k==-1而跳出循環時，next[j] = 0，否則next[j]會在break之前被賦值
        }
    }
    return next;
}

對于模式串T的下標 j 回退位置next[]的求解方法，KMP算法應用的動態規劃的思想：

首先大膽假設next[j]=k，則

那么next[j+1]=?

也就是以上子串再分別多考慮一個隨后的字符：

可以區分這兩個字符在相等和不等的情況下分別考慮：

有了確定模式串回退位置的數組，字符串匹配剩下的代碼就相對較容易了。

demo c code：

#include <stdio.h>
#include <malloc.h>
#include <string.h>
// 對主串s和模式串t進行KMP模式匹配
// 計算模式串t需要回退的位置（BF是回退到0）
int *getNextArray(char t[]) // 動態規劃
{
    int n = strlen(t);
    int *next = (int*)malloc(sizeof(int)*n);
    next[0] = -1;
    next[1] = 0;
    int k;
    for (int j = 2; j < n; j++) {
        k=next[j-1];            // 先假設
        while (k!=-1) {
            if (t[j - 1] == t[k]) {
                next[j] = k + 1;
                break;
            }else
                k = next[k];    // 回退
            next[j] = 0;  //當k==-1而跳出循環時，next[j] = 0，否則next[j]會在break之前被賦值
        }
    }
    return next;
}

/**
 * 對主串s和模式串t進行KMP模式匹配
 * @param s 主串
 * @param t 模式串
 * @return 若匹配成功，返回t在s中的位置（第一個相同字符對應的位置），若匹配失敗，返回-1
 */
int kmpMatch(char* s, char* t){
    int *next = getNextArray(t);
    int i = 0, j = 0;
    while (i<(int)strlen(s) && j<(int)strlen(t)){
        if(j == -1 || s[i]==t[j]){
            i++;
            j++;
        }
        else
            j = next[j];
    }
    //printf("ni-j = %d - %d = %dn",i,j,i-j);
    if(j == (int)strlen(t))
        return i-j;
    else
        return -1;
}
int main()
{
    //char* str[] = {"ACBACAACAACACAACAB","ACAACAB"};
    //char* str[] = {"abaabaabeca","abaabe"};
    char* str[] = {"abaabaeabaabea","abaabe"};
    int *next = getNextArray(str[1]);
    int i,j;
    printf("主串s[]=    ");
    for(i=0;i<(int)strlen(str[0]);i++)
        printf("%c ",str[0][i]);
    printf("n");
    for(i=0;i<2;i++)
    {
        printf("模式串t[]=  ");
        for(j=0;j<(int)strlen(str[1]);j++)
            printf("%c ",str[1][j]);
        printf("n");
    }
    printf("next[]   = ");
    for(i=0;i<strlen(str[1]);i++)
        printf("%d ",next[i]);
    int n = kmpMatch(str[0],str[1]);
    printf("n模式串t首次匹配到主串s的位置：%dn",n);
    getchar();
}
/*
主串s[]=    a b a a b a a b e c a
模式串t[]=  a b a a b e
模式串t[]=  a b a a b e
next[]   = -1 0 0 1 1 2
模式串t首次匹配到主串s的位置：3

主串s[]=    A C B A C A A C A A C A C A A C A B
模式串t[]=  A C A A C A B
模式串t[]=  A C A A C A B
next[]   = -1 0 0 1 1 2 3
模式串t首次匹配到主串s的位置：11

主串s[]=    a b a a b a e a b a a b e a
模式串t[]=  a b a a b e
模式串t[]=  a b a a b e
next[]   = -1 0 0 1 1 2
模式串t首次匹配到主串s的位置：7

*/

demo JAVA code：

class Ideone
{
    public static int[] getNextArray(char[] t) {
        int[] next = new int[t.length];
        next[0] = -1;
        next[1] = 0;
        int k;
        for(int j = 2; j < t.length; j++) {
            k=next[j-1];
            while(k!=-1) {
                if(t[j - 1] == t[k]) {
                    next[j] = k + 1;
                    break;
                }
                else {
                    k = next[k];
                }
                next[j] = 0;  //當k==-1而跳出循環時，next[j] = 0，否則next[j]會在break之前被賦值
            }
        }
        return next;
    }
    
    /**
    * 對主串s和模式串t進行KMP模式匹配
    * @return 若匹配成功，返回t在s中的位置（第一個相同字符對應的位置），若匹配失敗，返回-1
    */
    public static int kmpMatch(String s_arr, String t_arr){
        char[] s = s_arr.toCharArray();
        char[] t = t_arr.toCharArray();
        int[] next = getNextArray(t);
        for(int i=0;i<t.length;i++)
            System.out.print(next[i] + " ");
        int i = 0, j = 0;
        while(i<s.length && j<t.length){
            if(j == -1 || s[i]==t[j]){
                i++;
                j++;
            }
            else
                j = next[j];
        }
        System.out.printf("n%d %d %dn",i,j,t.length);
        if(j == t.length)
            return i-j;
        else
            return -1;
    }
	public static void main (String[] args) throws java.lang.Exception
	{
        int n = kmpMatch("ACBACAACAACACAACAB","ACAACAB");
        System.out.printf("%dn",n);
	}
}
/*
-1 0 0 1 1 2 3 
18 7 7
11
*/