[kuangbin带你飞]专题十六 KMP - L - Subs

【题目】kuangbin 带你飞 专题十六 -L - Substrings

思路

• 暴力就好了
• 用find也行，kmp也行，暂时还没有去研究它们的效率

AC代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    string str[105];
    while(T--){
        int N;
        cin>>N;
        for(int i = 0 ; i< N;i++){
            cin>>str[i];
        }
        int ans=0;
        int len = str[0].length();
        int flag = true; 
        for(int cnt = len;cnt>0;cnt--){
            for(int s = 0 ; cnt+s<=len ;s++ ){
                string T = str[0].substr(s,cnt);
                flag = true;
                for(int i = 1 ;i<N;i++){
                    if(str[i].find(T)==-1){
                        reverse(str[i].begin(),str[i].end());
                        if(str[i].find(T)==-1){
                            flag = false;
                            break;
                        } 
                                                    
                    }
                }
                if(flag == true){
                    ans = cnt;
                    break;
                }       
            }
            if(flag == true) break;
        }
        cout<<ans<<"\n";
    }
 }