时间戳

首页 > 技术文章 > ICPC Southeast USA 2020 Regional Contest problemI: Longest Common Subsequence(思维)

ICPC Southeast USA 2020 Regional Contest problemI: Longest Common Subsequence(思维)

UpMing 2021-04-12 12:49 原文

题目描述

You are given n strings, each a permutation of the first k upper-case letters of the alphabet.
String s is a subsequence of string t if and only if it is possible to delete some (possibly zero)characters from the string t to get the string s.
Compute the length of the longest common subsequence of all n strings.

输入

The first line of input contains two integers n (1 ≤ n ≤ 105 ) and k (1 ≤ k ≤ 26), where n is the number of strings, and the strings are all permutations of the first k upper-case letters of the alphabet.
Each of the next n lines contains a single string t. It is guaranteed that every t contains each of the first k upper-case letters of the alphabet exactly once.

输出

Output a single integer, the length of the longest subsequence that appears in all n strings.

样例输入 Copy

【样例1】
2 3
BAC
ABC
【样例2】
3 8
HGBDFCAE
ADBGHFCE
HCFGBDAE
【样例3】
6 8
AHFBGDCE
FABGCEHD
AHDGFBCE
DABHGCFE
ABCHFEDG
DGABHFCE

样例输出 Copy

【样例1】
2
【样例2】
3
【样例3】
4





就是求n个串的lcs，虽然串有2e5个，但是每个串最长有26而且每个字母只出现一次
在一个串中，我们统计所有的长度为2的子序列，然后从枚举一个字母为lcs的起点然后去找下一个满足的条件的字母，
比如a-b，那么a-b必须出现了n次，也就是我们最开始统计的东西

注意用set去重，因为串太多vector会T
map也可以，能达到去重效果就可以


CODE：
int n,m,ans;
int vis[27][27];
set<int>v[27];
void dfs(int x,int dep) {
    ans  = max(ans,dep);
    for(int y:v[x]) {
        if(vis[x][y]==n) {
            dfs(y,dep+1);
        }
    }    
}
int main() {
    n=read(),m=read();
    for(int i=1 ; i<=n ; i++) {
        string s;
        cin>>s;
        for(int j=0 ; j<s.size() ; j++) {
            for(int k=j+1 ; k<s.size(); k++) {
                int t1 = s[j] -'A' +1;
                int t2 = s[k] -'A' +1;
                vis[t1][t2]++;
                if(vis[t1][t2]==n) ans=1;
                v[t1].insert(t2);
            }
        }
    }
    for(int i=1 ; i<=26; i++ ) dfs(i,1);
    out(ans);
    return  0;
}
View Code

 




推荐阅读