• <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 - 183,  comments - 10,  trackbacks - 0

            求字符串中包含所有字符的最小全集子串
            http://www.vanjor.org/blog/2011/05/find-dic-substring/

            這其實也是一個最短文摘生成方法

            實現方式是:用兩個 left 和 right 指針順序掃描母字符串。
            時間復雜度:O(N)

            實現:

             

              1 #include <iostream>
              2 #include <string>
              3 #include <map>
              4 #include <cstring>
              5 using namespace std;
              6 
              7 string foo(const string& s, const string& t)
              8 {
              9     int tmap[256], ts[256];
             10     memset(tmap, 0sizeof (tmap));
             11     memset(ts,   0sizeof (ts));
             12     int tSize = 0;
             13     for (string::size_type i = 0; i != t.size(); ++i)
             14     {
             15         if (tmap[t[i]] == 0)
             16         {
             17             tmap[t[i]] = 1;
             18             ++tSize;
             19         }
             20     }
             21     string::size_type left = 0, right = s.size() - 1, i = 0, j = 0;
             22     int count = 0;
             23     while (i < s.size() && tmap[s[i]] == 0)
             24     {
             25         ++i;
             26     }
             27     if (i >= s.size())
             28     {
             29         return string("Not found!");
             30     }
             31     bool find = false;
             32     for (j = i; j < s.size(); ++j)
             33     {
             34         if (tmap[s[j]] == 1)
             35         {
             36             ++ts[s[j]];
             37             if (ts[s[j]] == 1)
             38             {
             39                 ++count;
             40                 if (count == tSize)
             41                 {
             42                     find = true;
             43                     if (j - i < right - left)
             44                     {
             45                         left = i;
             46                         right = j;
             47                     }
             48                     while (i < s.size())
             49                     {
             50                         if (tmap[s[i]] == 1)
             51                         {
             52                             --ts[s[i]];
             53                             if (ts[s[i]] == 0)
             54                             {
             55                                 --count;
             56                                 if (j - i < right - left)
             57                                 {
             58                                     left = i;
             59                                     right = j;
             60                                 }
             61                                 ++i;
             62                                 break;
             63                             }
             64                         }
             65                         ++i;
             66                     }
             67                     while (i < s.size() && tmap[s[i]] == 0)
             68                     {
             69                         ++i;
             70                     }
             71                     if (i >= s.size())
             72                     {
             73                         if (find)
             74                         {
             75                             return s.substr(left, right - left + 1);
             76                         }
             77                         else
             78                         {
             79                             return string("Not found!");
             80                         }
             81                     }
             82                 }
             83             }
             84         }
             85     }
             86     if (find)
             87     {
             88         return s.substr(left, right - left + 1);
             89     }
             90     else
             91     {
             92         return string("Not found!");
             93     }
             94 }
             95 
             96 int main()
             97 {
             98     string s, t;
             99     while (cin >> s >> t)
            100     {
            101         cout << foo(s, t) << endl;
            102     }
            103 
            104     return 0;
            105 }

             



            ===
            http://www.vanjor.org/blog/2011/05/sorting-collections/
            http://www.vanjor.org/blog/2011/05/find-dic-substring/
            http://coolshell.cn/articles/3933.html
            http://coolshell.cn/
            http://jsdo.it/norahiko/oxIy/fullscreen
            http://jsdo.it/
            posted on 2011-12-28 23:12 unixfy 閱讀(641) 評論(0)  編輯 收藏 引用
            久久久久女教师免费一区| 日产精品久久久一区二区| 精品国产综合区久久久久久| 国内精品久久久久久久亚洲| 伊人久久大香线蕉成人| 久久久久久久亚洲Av无码| 国产免费久久久久久无码| 国产aⅴ激情无码久久| AAA级久久久精品无码片| 亚洲国产成人久久一区WWW| 久久久精品人妻一区二区三区蜜桃| 亚洲精品国产成人99久久| 亚洲伊人久久大香线蕉综合图片| 久久夜色tv网站| 久久婷婷国产综合精品| 欧美午夜A∨大片久久 | 国产亚洲欧美成人久久片| 久久久久久久久66精品片| 热99re久久国超精品首页| 亚洲va久久久噜噜噜久久男同 | 欧美日韩精品久久免费| 国产精品美女久久久网AV| 无码伊人66久久大杳蕉网站谷歌| 国产成人99久久亚洲综合精品| 日韩精品久久久久久久电影蜜臀| 日韩人妻无码精品久久久不卡| 国产精品九九久久免费视频 | 久久久久久综合一区中文字幕| 久久精品亚洲AV久久久无码| 久久精品国产亚洲7777| 香港aa三级久久三级| 97久久超碰国产精品旧版| 人妻无码中文久久久久专区| 久久亚洲AV成人无码| 久久亚洲精品国产精品婷婷| 亚洲欧美另类日本久久国产真实乱对白 | 色婷婷综合久久久久中文| 精品国产青草久久久久福利| 色播久久人人爽人人爽人人片AV| 久久精品视频91| 久久久精品人妻一区二区三区蜜桃|