青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

枯葉北風寒,忽然年以殘,念往昔,語默心酸。二十光陰無一物,韶光賤,寐難安; 不畏形影單,道途阻且慢,哪曲折,如渡飛湍。斬浪劈波酬壯志,同把酒,共言歡! -如夢令

深度剖析KMP,讓你認識真正的Next

KMP算法,想必大家都不陌生,它是求串匹配問題的一個經(jīng)典算法(當然如果你要理解成放電影的KMP,請退出本頁面直接登錄各大電影網(wǎng)站,謝謝),我想很多人對它的理解僅限于此,知道KMP能經(jīng)過預處理然后實現(xiàn)O(N*M)的效率,比brute force(暴力算法)更優(yōu)秀等等,其實KMP算法中的Next函數(shù),功能十分強大,其能力絕對不僅僅限于模式串匹配,它并不是KMP的附屬品,其實它還有更多不為人知的神秘功能^_^

先來看一個Next函數(shù)的典型應用,也就是模式串匹配,這個相信大家都很熟悉了:
POJ 3461 Oulipo——很典型的模式串匹配問題,求模式串在目標串中出現(xiàn)的次數(shù)。

#include<cstdio>
#include
<iostream>
#include
<cmath>
#include
<cstring>
#include
<algorithm>
using namespace std;
#define MAX 1000001

char t[MAX];
char s[MAX];
int next[MAX];
inline 
void calnext(char s[],int next[])
{
    
int i;
    
int j;
    
int len=strlen(s);
    next[
0]=-1;
    j
=-1;
    
for(i=1;i<len;i++)
    
{
        
while(j>=0&&s[i]!=s[j+1])
            j
=next[j];
        
if(s[j+1]==s[i])//上一個循環(huán)可能因為j=-1而不做,此時不能知道s[i]與s[j+1]的關系。故此需要此條件。
            j++;
        next[i]
=j;
    }

}



int KMP(char t[],char s[])
{
    
int ans=0;
    
int lent=strlen(t);
    
int lens=strlen(s);
    
if(lent<lens)
        
return 0;
    
int i,j;
    j
=-1;
    
for(i=0;i<lent;i++)
    
{

        
while(j>=0&&s[j+1]!=t[i])
            j
=next[j];
        
if(s[j+1]==t[i])
            j
++;
        
if(j==lens-1)
        
{
            ans
++;
            j
=next[j];
        }

    }

    
return ans;

}



int main()
{

    
int testcase;
    scanf(
"%d",&testcase);
    
int i;
    
for(i=1;i<=testcase;i++)
    
{
    
        scanf(
"%s%s",s,t);
        calnext(s,next);
        printf(
"%d\n",KMP(t,s));
    }

    
return 0;

}

——————————————————————————————————————————————————————————————————————————————————————
POJ 2406 Power Strings
這道題就比較有意思了,乍看之下,怎么看貌似都與KMP無關,呵呵,這就是因為你沒有深入理解Next 的含義;
我首先來解釋下這道題的題意,給你一個長度為n的字符串,首先我們找到這樣一個字符串,這個字符串滿足長度為n的字符串是由這個字符串重復疊加得到并且這個字符串的長度要最小.,然后輸出重復的次數(shù)。
比如說,ababab這個字符串,顯然它是由ab重復疊加3次得到,所以,答案輸出3.

那么這個題用next怎么做呢,我們必須知道,next數(shù)組里面存放的是 如果當前匹配失敗,模式串可以繼續(xù)進行匹配的下一個位置。
For Example:
        1 2 3 4 5 6
     S= a b a b a ?
  Next= 0 0 1 2 3
其中next[5]=3,說明如果模式串在j=6處匹配失敗,那么j=next[5]=3 ,為什么? 因為S的頭三位和末三位是一樣的,如果說S已經(jīng)匹配到5的位置(匹配到5說明前5位都已經(jīng)匹配上),那么前三位肯定也匹配上了(廢話~),若果這個時候要繼續(xù)匹配,我們可以將模式串向右平移幾個個單位,這樣保證S的前三位仍然是可以匹配上的。

比如說目標串是

    i=  1  2  3  4  5  6  7  8  9 
         a  b  a   b  a  d  e  f   g
         a  b  a   b  a  c
    j=  1  2  3  4  5  6
next= 0  0  1  2  3  ? 
現(xiàn)在我們發(fā)現(xiàn)i=6與j=6兩串不匹配怎么辦?由于next[5]指向3,那么我們將模式串平移
    i=  1  2  3  4  5  6  7  8  9 
         a  b  a   b  a  d  e  f   g
                 a   b  a  b  a  c   
           
j=  1  2  3  4  5  6
        next= 0  0  1  2  3  ? 
這樣我們從j=3處繼續(xù)向后匹配。(當然如果此時i=6與j=4仍然不匹配,那么我們繼續(xù)使用失敗函數(shù),去尋找下一個位置)

 好的,現(xiàn)在我們已經(jīng)知道了,next數(shù)組中所存放的數(shù)字的含義,那么接下來讓我們來看看怎樣靈活的使用next,揭開它不為人知的另一面吧。
回到原題,原題要求求出一個字符串的某一個子串,使得這個字符串不斷自我疊加后得到原串,并且這個重復的次數(shù)最多。那么它和next有什么關系呢???

結(jié)論:如果有一個字符串s,長度是len,它的失敗函數(shù)是next,如果len能被len-next[len]整除,那么len-next[len]就是我們要求的那個子串的長度,與之對應的字符串,就是我們想得到的子串;

為什么呢? 假設我們有一個字符串a(chǎn)babab,那么next[6]=4對吧,由于next的性質(zhì)是,匹配失敗后,下一個能繼續(xù)進行匹配的位置,也就是說,把字符串的前四個字母,abab,平移2個單位,這個abab一定與原串的abab重合(否則就不滿足失敗函數(shù)的性質(zhì)),這說明了什么呢,由于字符串進行了整體平移,而平移后又要重疊,那么必有
s[1]=s[3],s[2]=s[4],s[3]=s[5],s[4]=s[6].說明長度為2的字符串在原串中一定重復出現(xiàn),這就是len-next[len]的含義!
解決上面這個問題的同時,其實還有另一個問題,那就是如果這個字符串長度為奇數(shù)怎么辦?如ababa,好像next[len]也等于3呢,可是aba-ba-似乎并不是由ba重復得到的吧。我們先把這個字符串斷開,ab-ab-a,可以想象,中間的ab平移后,沒有ab與它重合(只能重合一個,這雖然沒有違背next的性質(zhì),但是卻對本題的方法造成了影響,請讀者細細品味),所以才會出現(xiàn)上面的情況!所以要加上len能夠整除len-next[len]這個條件.

此題源代碼如下:
//This is the source code for POJ 2406
//coded by abilitytao
//2009年7月31日11:17:34
#include<cstdio>
#include
<iostream>
#include
<cmath>
#include
<cstring>
#include
<algorithm>
using namespace std;
#define MAX 1000001

int next[MAX];
inline 
void calnext(char s[],int next[])
{
    
int i;
    
int j;
    
int len=strlen(s);
    next[
0]=-1;
    j
=-1;
    
for(i=1;i<len;i++)
    
{
        
while(j>=0&&s[i]!=s[j+1])
            j
=next[j];
        
if(s[j+1]==s[i])
            j++;
        next[i]
=j;
    }

}



int main()
{
    
int n;
    
char str[MAX];
    
int len;
    
while(scanf("%s",&str))
    
{
        
if(str[0]=='.')
            
break;
        len
=strlen(str);
        calnext(str,next);
        
if((len)%(len-1-next[len-1])==0)
            printf(
"%d\n",(len)/(len-1-next[len-1]));
        
else 
        
{
            putchar(
'1');
            putchar(
'\n');
        }


    }

    
return 0;
    
}



POJ 1961與上題類似,故不贅述,代碼如下:
//This is the source code for POJ 1961
//coded by abilitytao
//2009年7月31日10:56:07
#include<cstdio>
#include
<iostream>
#include
<cmath>
#include
<cstring>
#include
<algorithm>
using namespace std;
#define MAX 1000001

int next[MAX];
void calnext(char s[],int next[])
{
    
int i;
    
int j;
    
int len=strlen(s);
    next[
0]=-1;
    j
=-1;
    
for(i=1;i<len;i++)
    
{
        
while(j>=0&&s[i]!=s[j+1])
            j
=next[j];
        
if(s[j+1]==s[i])
            j
++;
        next[i]
=j;
    }

}



int main()
{
    
int n;
    
char str[MAX];
    
int casenum=0;
    
int i;
    
int len;
    
while(scanf("%d",&n))
    
{
        casenum
++;
        
        
if(n==0)
            
break;
        scanf(
"%s",str);
        len
=strlen(str);
        printf(
"Test case #%d\n",casenum);
        calnext(str,next);
        
for(i=1;i<len;i++)
        
{
            
            
if((i+1)%(i-next[i])==0&&next[i]!=-1)
                printf(
"%d %d\n",i+1,(i+1)/(i-next[i]));
        }

        printf(
"\n");
    }

    
return 0;
    
}




POJ 2752 Seek the Name, Seek the Fame
這道題揭開了next的另一個應用^_^
題目的意思可以這樣描述:給出一個字符串S,長度為len;找出一個前綴一個后綴,使得這兩個字符串相同。 輸出所有可能的情況。

如aaaaa,
aaaaa ——》OK
aaaaa ——》OK
aaaaa + aaaaa  ——》OK
aaaaa + aaaaa  ——》OK
aaaaa + aaaaa ——》OK

那么這個題怎么用next呢,其實很簡單,只要你知道next的含義。 s[1]——s[next[len]]中的內(nèi)容一定能與s[1+len-next[len]]——s[len]匹配,所以s[1]——s[next[len]]就是我們要求取的最長的那個串,然后呢我們循環(huán)地利用next,由于next的性質(zhì),可以保證,每一次得出的字串都能匹配到最后一個字母,也就是得到一個前綴等于后綴。只不過這個字符串的長度在不斷地減小罷了。不斷地使用next我們直到求出所有的前綴^_^  So the problem is cleared.

附源代碼:

//This is the source code for POJ 2752
//coded by abilitytao
//2009年7月31日12:17:45

#include
<cstdio>
#include
<iostream>
#include
<cmath>
#include
<cstring>
#include
<algorithm>
using namespace std;
#define MAX 1000001

int next[MAX];
inline 
void calnext(char s[],int next[])
{
    
int i;
    
int j;
    
int len=strlen(s);
    next[
0]=-1;
    j
=-1;
    
for(i=1;i<len;i++)
    
{
        
while(j>=0&&s[i]!=s[j+1])
            j
=next[j];
        
if(s[j+1]==s[i])//上一個循環(huán)可能因為j=-1而不做,此時不能知道s[i]與s[j+1]的關系。故此需要此條件。
            j++;
        next[i]
=j;
    }

}



int record[MAX];


int main()
{
    
char str[MAX];
    
int len;
    
int p=0;
    
int j;
    
while(scanf("%s",&str)!=EOF)
    
{
        calnext(str,next);
        p
=0;
        len
=strlen(str);
        j
=len-1;

        
while(j!=-1)
        
{
            record[
++p]=j;
            j
=next[j];
        }

        
while(p>1)
        

            printf(
"%d ",record[p]+1);
            p
--;
        }

            printf(
"%d\n",record[p]+1);
    }

    
return 0;
    
}


文章寫完了,如果有什么疏漏,還請大家批評指正~
文章來自abilitytao博客
轉(zhuǎn)載請注明出處:http://www.shnenglu.com/abilitytao/archive/2009/08/01/91865.html

posted on 2009-08-01 10:26 abilitytao 閱讀(3077) 評論(3)  編輯 收藏 引用

評論

# re: 深度剖析KMP,讓你認識真正的Next 2009-08-01 10:29 凡客誠品

不錯啊  回復  更多評論   

# re: 深度剖析KMP,讓你認識真正的Next 2009-08-01 16:09 Vincent

ac自動機,擴展kmp  回復  更多評論   

# re: 深度剖析KMP,讓你認識真正的Next 2009-08-01 16:56 abilitytao

@Vincent
呵呵 自動機絕對很強大的  回復  更多評論   

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲视频在线观看网站| 国产乱码精品一区二区三| 黄色一区二区在线| 久久久久久久久蜜桃| 久久精品视频免费播放| 亚洲福利一区| 日韩午夜在线电影| 国产精品日韩专区| 浪潮色综合久久天堂| 欧美国产激情| 亚洲免费视频网站| 欧美在线观看视频在线| 亚洲国产视频一区二区| 亚洲另类春色国产| 国产婷婷色综合av蜜臀av| 麻豆精品精华液| 欧美日韩国产成人| 久久久99爱| 欧美高清自拍一区| 欧美中文在线免费| 欧美成人精品在线播放| 欧美一区二区免费| 欧美成人午夜激情在线| 欧美日韩国产综合在线| 欧美一区二区私人影院日本 | 欧美jjzz| 欧美日韩一区二区三区四区五区 | 久久国产乱子精品免费女 | 一区二区免费在线视频| 韩国久久久久| 国产精品99久久久久久久女警| 国产九色精品成人porny| 欧美成人精品一区二区| 国产精品伊人日日| 亚洲精品护士| 亚洲第一网站免费视频| 亚洲最新在线| 亚洲精品在线免费| 久久久精品日韩欧美| 亚洲一区二区视频| 欧美激情日韩| 美女成人午夜| 黑人一区二区三区四区五区| 中国成人在线视频| 99精品黄色片免费大全| 久久综合久久综合久久综合| 欧美亚洲一区| 国产精品爱啪在线线免费观看 | 亚洲视频一区在线观看| 美女诱惑一区| 免费观看在线综合色| 国产免费成人在线视频| 一区二区三区欧美在线| 99视频精品全部免费在线| 久久在线视频| 欧美二区在线观看| 亚洲国产成人av| 久久精品视频99| 玖玖国产精品视频| 伊人成人网在线看| 欧美影院在线播放| 久久午夜电影| 在线免费观看欧美| 久久婷婷国产综合尤物精品| 美女久久网站| 亚洲激情电影中文字幕| 欧美1级日本1级| 欧美xx69| 夜夜嗨av一区二区三区四季av| 欧美第一黄色网| 91久久香蕉国产日韩欧美9色| 亚洲人在线视频| 欧美麻豆久久久久久中文| 亚洲精品久久| 欧美一级大片在线免费观看| 国产精品网站视频| 欧美影视一区| 亚洲国产欧美精品| 亚洲性色视频| 国内精品久久久久影院薰衣草 | 亚洲精品激情| 欧美亚洲一区在线| 一区二区自拍| 亚洲电影免费观看高清完整版在线| 在线精品观看| 欧美日韩亚洲天堂| 欧美亚洲视频在线观看| 另类酷文…触手系列精品集v1小说| 在线日韩电影| 欧美日韩综合视频| 久久国产一区二区| 91久久久久久久久久久久久| 亚洲免费婷婷| 亚洲国产成人久久综合一区| 欧美日韩精品免费| 欧美自拍偷拍| 亚洲日本成人女熟在线观看| 性欧美1819sex性高清| 在线日韩欧美视频| 国产精品久线观看视频| 一区二区三区|亚洲午夜| 欧美精品在线一区| 国内精品国语自产拍在线观看| 亚洲九九精品| 在线观看av不卡| 欧美国产先锋| 亚洲一区二区三区四区中文| 国产精品久久毛片a| 久久久久免费观看| a4yy欧美一区二区三区| 久久久综合网| 午夜精品久久久久久久99黑人| 亚洲福利视频在线| 国产欧美日韩在线播放| 欧美高清在线一区| 久久免费99精品久久久久久| 夜夜嗨一区二区| 欧美多人爱爱视频网站| 久久精品亚洲一区二区| 亚洲视频一二| 日韩一区二区精品在线观看| 国自产拍偷拍福利精品免费一| 欧美日韩亚洲一区二区三区在线观看| 久久久综合网站| 欧美在线free| 欧美一级专区免费大片| 亚洲一区二区少妇| 99精品国产在热久久| 欧美激情1区2区| 久久亚洲精品视频| 久久精品成人| 久久精品99国产精品日本| 亚洲欧美综合精品久久成人 | 免费观看日韩av| 久久精品在这里| 欧美色大人视频| 你懂的国产精品| 一区二区三区四区五区精品视频 | 99精品福利视频| 91久久精品一区二区别| 怡红院精品视频在线观看极品| 国产日本欧美视频| 国产日韩欧美| 国产最新精品精品你懂的| 国产日韩综合一区二区性色av| 国产精品日韩欧美| 国产拍揄自揄精品视频麻豆| 国产精品一区二区在线观看| 国产精品久久久一区二区| 国产伦一区二区三区色一情| 国产精品自在在线| 国产欧美日韩综合| 国产一区二区三区在线免费观看 | 在线亚洲观看| 亚洲影视综合| 久久精品国产亚洲5555| 久久亚洲精品中文字幕冲田杏梨| 久久久久久久性| 美女精品在线| 欧美日韩中文字幕在线视频| 国产精品免费在线| 黄色资源网久久资源365| 亚洲经典在线| 午夜在线a亚洲v天堂网2018| 久久精品1区| 欧美不卡在线| 中文一区二区在线观看| 欧美在线观看一二区| 欧美成人午夜免费视在线看片| 欧美日韩成人在线播放| 国产精品一区二区久久| 一区视频在线播放| 一区二区三区四区国产| 欧美在线3区| 亚洲电影免费观看高清完整版在线 | 久久久99爱| 亚洲精品乱码久久久久| 亚洲一区二区精品在线| 久久亚洲综合色| 国产精品国码视频| 樱桃视频在线观看一区| 一本色道久久加勒比88综合| 久久国产欧美日韩精品| 亚洲国产精品久久精品怡红院| 一区二区精品国产| 欧美aa在线视频| 国产婷婷色一区二区三区| 一区二区三区 在线观看视频| 久久精品亚洲一区二区三区浴池| 亚洲六月丁香色婷婷综合久久| 性欧美videos另类喷潮| 欧美日韩中文字幕日韩欧美| 亚洲风情在线资源站| 欧美一区二区三区在| 亚洲日本va午夜在线电影| 久久婷婷麻豆| 精品99一区二区三区| 欧美在线影院| 亚洲欧美激情在线视频| 欧美另类在线播放|