hdu 3336 KMP入門 DP

2022-11-24 21:41:16 字數 623 閱讀 5130

例3:i :     123456789

字串:     ababcdabd 

next[i]:     001200120

dp: 

cns陣列:以 i 結尾的串中所有字首的計數和

狀態轉移方程:  cns[i] = cns[next[i]] + 1;

i :     123456

字串:    ababab   

cns[i]:    112233

比如當i等於5時,ababa中後面的aba與前面的aba重疊,  

以第三個a為結尾的字首總數對應於前面的aba的字首數+1(ababa)

#include #include const int max_len = 200005;	

int next[max_len];

char s[max_len];

int cns[max_len];

int main()

int sum=0;

memset(cns,0,sizeof(cns));

for(int i=1;i<=len;i++)

printf("%d\n",sum);

} return 0;

}

HDU 3336 KMP

題意 求每一個字首,跟字首相同的每個子串。此題 網上很多都是假程式,不過也ac了,的確我測試幾個案例之後的的確確是存在這個問題。分析 每一個字首,可以考慮kmp,f失配指標,如何求得它出現了多少次呢?如果f 0 至少這個字首是符合的,但是,你會少算一些,例如 你會少運算元串a,怎麼彌補回來呢?繼續遞...

hdu 3336 kmp next陣列應用

分析 十分易懂 題意 求字串中 字首 跟字首相同的子串 的個數?sample input14 abab sample output 6abab 包括2個a,2個ab,1個aba,1個abab 這裡要用到next值的意義 next i 表示前i個字元所組成的字串的最大前字尾匹配長度 舉個例子 next...

hdu5763 kmp dp

先說說kmp模板,本質就是先求小字串的next陣列,即對每個位置i,next i 以i位置為終點,字首和字尾相等的最大長度 求出之後以小字串為基準類似去求大字串的next,即把小字串放到大字串前面求next陣列,當大字串的某一個位置的next是大於等於小字串長度時則含有小字串,這個位置至少要在大字串...