kuangbin专题十六 KMP&&扩展KMP HDU1238 Substrings

You are given a number of case-sensitive strings of alphabetic characters, find the largest string X, such that either X, or its inverse can be found as a substring of any of the given strings.

InputThe first line of the input file contains a single integer t
(1 <= t <= 10), the number of test cases, followed by the input
data for each test case. The first line of each test case contains a
single integer n (1 <= n <= 100), the number of given strings,
followed by n lines, each representing one string of minimum length 1
and maximum length 100. There is no extra white space before and after a
string.

OutputThere should be one line per test case containing the length of the largest string found.

Sample Input

2

3

ABCD

BCDFF

BRCD

2

rose

orchid

Sample Output

2

2

这道题和之前一道题类似，都是多个字符串匹配问题，只是这道题多了倒序的匹配。直接reverse就可以了
遍历第一个串的所有后缀，然后匹配每个字符串的正反序。得到公共匹配的最小。然后枚举所有后缀取最大

 #include<stdio.h>

 #include<iostream>

 #include<string>

 #include<algorithm>

 #include<vector>

 using namespace std;

 int _,n,Next[];

 vector<string> t;

 void prekmp(string s) {

     int len=s.size();

     int i,j;

     j=Next[]=-;

     i=;

     while(i<len) {

         while(j!=-&&s[i]!=s[j]) j=Next[j];

         Next[++i]=++j;

     }

 }

 int kmp(string t,string p) {

     int lent=t.size(),lenp=p.size();

     int i=,j=,ans=-,res;

     res=-;

     while(i<lent) {

         while(j!=-&&t[i]!=p[j]) j=Next[j];

         ++i;++j;

         res=max(res,j);

     }

     ans=max(ans,res);

     reverse(t.begin(),t.end());

     res=-;

     i=,j=;

     while(i<lent) {

         while(j!=-&&t[i]!=p[j]) j=Next[j];

         ++i;++j;

         res=max(res,j);

     }

     ans=max(ans,res);

     return ans;

 }

 int main() {

    // freopen("in","r",stdin);

     for(scanf("%d",&_);_;_--) {

         scanf("%d",&n);

         string s;

         for(int i=;i<n;i++) {

             cin>>s;

             t.push_back(s);

         }

         string str=t[],tempstr;

         int len=str.size(),maxx=-;

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

             tempstr=str.substr(i,len-i);

             int ans=0x3f3f3f;

             prekmp(tempstr);

             for(int j=;j<t.size();j++) {

                 ans=min(kmp(t[j],tempstr),ans);

             }

             maxx=max(maxx,ans);

         }

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

         t.clear();

     }

 }

巴特西

kuangbin专题十六 KMP&&扩展KMP HDU1238 Substrings

最新文章

热门文章