HDU-2328-Corporate Identity(利用string函数)

博主链接

题目链接

题意：

给你n个字符串，问你这n个串的最长公共子串

题解：

题目和HDU-1238感觉差不多，暴力枚举任意一个字符串的所有子串，然后暴力匹配，这里用string解决的；

代码：

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=4050;
const int mod=1e9+7;
string s[maxn];
int main(){
    int n;
    ios::sync_with_stdio(0);
    while((cin>>n)&&n!=0){
        for(int i=1;i<=n;i++){
            cin>>s[i];
        }
        string t;
        int cot=0;
        int maxx=0;
        int len=s[1].size();
        for(int i=0;i<len;i++){
            for(int j=1;j<=len-i;j++){      //枚举子串长度
                if(j<maxx)continue;
                cot=0;
                for(int k=2;k<=n;k++){
                    if(s[k].find(s[1].substr(i,j))==string::npos)break; //string函数查找
                    else cot++;
                }
                if(cot==n-1){	//如果这个子串出现了n-1次，选取的那个串本身就有一次，则维护maxx
                    if(maxx<j){		
                        maxx=j;
                        t=s[1].substr(i,j);
                    }
                    else if(maxx==j){
                        if(t>s[1].substr(i,j))t=s[1].substr(i,j);
                    }
                }
            }
        }
        if(maxx==0)cout<<"IDENTITY LOST"<<endl;
        else cout<<t<<endl;
    }
    return 0;
}