• <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>
            posts - 43,  comments - 9,  trackbacks - 0
            后綴數組,KMP擴展,自動機
            題目要求4000個長度為200的字串的最長公共子串.
            只需選一個串作為基串, 枚舉它的所有后綴串S[i..len], 求出其它串與這個子串的LCP. 最后選最大的輸出.
            關于求串S與串T所有后綴的LCP, 林希德的論文講了擴展KMP算法. 不過我想出另一種方法:
            把S和T直接連接得到新串U. 按正常KMP的方法求U的next數組, 不過當p指向U[len[S]+1]即原T串的首字母時, 直接將此位的next置為0.
            最后min(len[S], next[k]) 就是串T[1..(k-len[S])]與串S的lcp長度.

            代碼如下:

             1#include <iostream>
             2using namespace std;
             3
             4char wd[4000][201];
             5int cnt[201][201], vis[201][201];
             6char ss[401];
             7int next[401];
             8int N;
             9
            10bool readin()
            11{
            12  scanf("%d",&N);
            13  if(N==0)return false;
            14  
            15  for(int i=0; i<N; i++)
            16    scanf("%s",wd[i]);
            17  return true;
            18}

            19
            20int mycmp(char *s1, int l1, char *s2, int l2)
            21{
            22  if(l1!=l2) return (l2-l1);
            23  while(--l1 && *s1==*s2) s1++, s2++;
            24  return (*s1-*s2);
            25}

            26
            27void mycpy(char *s1, char *s2, int l)
            28{
            29  while(l--*(s1++)=*(s2++);
            30  *s1=0;
            31}

            32
            33void solve()
            34{
            35  memset(cnt,0,sizeof(cnt));
            36  memset(vis,0,sizeof(vis));
            37  
            38  int l0=strlen(wd[0]);
            39  strcpy(ss,wd[0]);
            40  char ans[201]="";
            41  
            42  for(int p=0; p<l0; p++){
            43    char *s=&ss[p];
            44    for(int i=1; i<N; i++){
            45      strcpy(&ss[l0], wd[i]); //連接兩個串
            46      int l1=l0-p+strlen(wd[i]);
            47      next[0]=-1;
            48      int p0=-1, p1=0;
            49      while(p1<l1){
            50        while(p0>=0 && s[p0]!=s[p1])
            51          p0=next[p0];
            52        next[++p1]=++p0;
            53        if(p1==l0-p) //此位置0
            54          next[p1]=0, p0=0;
            55        if(p1>=l0-p){
            56          int len=min(l0-p, next[p1]);
            57          if(vis[p][p+len-1]!=i)
            58            vis[p][p+len-1]=i, cnt[p][p+len-1]++;
            59        }

            60      }

            61    }

            62    
            63    for(int j=l0-1; j>=p; j--){
            64      if(cnt[p][j]==N-1){
            65        if(mycmp(&ss[p], j-p+1, ans, strlen(ans))<0)
            66          mycpy(ans, &ss[p], j-p+1);
            67      }

            68    }

            69  }

            70  
            71  if(ans[0]==0)
            72    puts("IDENTITY LOST");
            73  else
            74    puts(ans);
            75}

            76
            77int main()
            78{
            79  while(readin()){
            80    solve();
            81  }

            82}

            83


            posted on 2009-07-31 13:46 wolf5x 閱讀(703) 評論(0)  編輯 收藏 引用 所屬分類: acm_icpc
            <2009年7月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            "Do not spend all your time on training or studying - this way you will probably become very exhausted and unwilling to compete more. Whatever you do - have fun. Once you find programming is no fun anymore – drop it. Play soccer, find a girlfriend, study something not related to programming, just live a life - programming contests are only programming contests, and nothing more. Don't let them become your life - for your life is much more interesting and colorful." -- Petr

            留言簿(3)

            隨筆分類(59)

            隨筆檔案(43)

            cows

            搜索

            •  

            最新評論

            評論排行榜

            久久人爽人人爽人人片AV| 久久人人爽人人爽人人AV东京热| www.久久热.com| 久久99久久成人免费播放| 久久精品国产亚洲AV影院| 精品国产乱码久久久久久郑州公司 | 伊人久久综合精品无码AV专区| 伊人久久大香线蕉AV色婷婷色| …久久精品99久久香蕉国产| 久久久久香蕉视频| 97久久超碰成人精品网站| 国产免费久久久久久无码| 无码国内精品久久综合88| 国产91色综合久久免费| 亚洲国产成人久久精品99 | 色综合久久88色综合天天 | 97精品依人久久久大香线蕉97| 天天久久狠狠色综合| 无码人妻少妇久久中文字幕蜜桃| 久久99精品免费一区二区| 亚洲AV无码久久精品蜜桃| 国产成人精品久久综合| 国产精品久久久久久吹潮| 亚洲精品97久久中文字幕无码| 夜夜亚洲天天久久| 国产精品久久久久久一区二区三区 | 亚洲伊人久久成综合人影院| 久久精品草草草| 99re久久精品国产首页2020| 无码人妻久久一区二区三区免费丨 | 国内精品伊人久久久影院| 国产精品美女久久久免费| 精品亚洲综合久久中文字幕| 久久综合精品国产二区无码| 精品国产99久久久久久麻豆| 久久精品18| 久久一区二区免费播放| 亚洲国产成人久久一区WWW| 久久精品一区二区三区中文字幕| 精品无码久久久久久久久久| 久久99精品久久久久久噜噜|