程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1618 Oulipo KMP題解

HDU 1618 Oulipo KMP題解

編輯:C++入門知識

HDU 1618 Oulipo KMP題解


給出兩個字符串,尋找一個字符串在另外一個字符串出現的頻率。

原來kmp還有一個陷阱,下面注釋出了,下標沒步進好,就有一定幾率出現超時的,也有一定幾率出現錯誤,視具體的串而定。

修改一下就好了,kmp速度是很快的。


#include 
#include 
    
const int MAX_TXT = 1000001;
const int MAX_WORD = 10001;
int gWlen, gTlen;
char word[MAX_WORD];
int next[MAX_WORD];
char txt[MAX_TXT];

void getNext()
{
    memset(next, 0, sizeof(int) * gWlen);
    for (int i = 1, j = 0; i < gWlen; )
    {
        if (word[i] == word[j]) next[i++] = ++j;
        else if (j > 0) j = next[j-1];
        else i++;
    }
}

int kmpSearch()
{
    int i = 0, j = 0, ans = 0;
    for (; gWlen-j <= gTlen-i; )
    {
        if (word[j] == txt[i])
        {
            j++; i++;
            if (j == gWlen)
            {
                ans++;
                j = next[j-1];
            }
            //else i++; i++放這裡會超時,是一定幾率會出現超時,注意了!
        }
        else if (j > 0) j = next[j-1];
        else i++;
    }
    return ans;
}

int main()
{
    int T;
    scanf("%d", &T);
    getchar();
    while (T--)
    {
        gets(word);
        gWlen = strlen(word);
        gets(txt);
        gTlen = strlen(txt);

        getNext();
        printf("%d\n", kmpSearch());
    }
    return 0;
}



  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved