北京林业大学“计蒜客”杯程序设计竞赛网络赛 D-A letter from Chensg【最长公共子序列LCS】

Love The Way You Lie 2022-08-21 11:41 114阅读 0赞

Can it really be 2 years since I first saw you? I still remember, vividly, 2 years ago, from the moment I saw you smile, as you were walking out of the classroom and turned your head back, with the soft sunset glow shining on your rosy cheek, I knew, I knew that I was already drunk on you. Then, after several months' observation and prying, your grace and your wisdom, your attitude to life and your aspiration for future were all strongly impressed on my memory. You were the glamorous and sunny girl whom I always dream of to share the rest of my life with. Alas, actually you were far beyond my wildest dreams and I had no idea about how to bridge that gulf between you and me. So I schemed nothing but to wait, to wait for an appropriate opportunity. Till now, I realize I am such an idiot that one should create the opportunity and seize it instead of just waiting?

Nowadays, you are planning to fly far far away, to pursue your future and fulfill your dreams. Perhaps we will not speak with each other very often if without fate and luck. Sometimes, I wandered around corridor hoping to meet you there by chance. But contradictorily, your appearance must quicken my heartbeat and my clumsy tongue might be not able to belch out a word. I cannot remember how many times I have passed your dormitory , and each time aspired to see you appear in the corridor. I cannot remember how many times this idea comes to my mind: call her out to have dinner or at least a conversation. But each time, thinking of your excellence and my commonness, the predominance of timidity over courage drove me leave silently?

Graduation, means the end of life in university, the end of these glorious, romantic years. Your lovely smile which is my original incentive to work hard and this unrequited love will be both sealed as a memory in the deep of my heart and my mind. Graduation, also means a start of new life, a footprint on the way to bright prospect. I truly hope you will be happy everyday abroad and everything goes well. Meanwhile, I will try to get out from puerility and become more sophisticated. To pursue my own love and happiness here in reality will be my ideal I never desert?

Good luck, my princess!?

If someday, somewhere, we have a chance to gather, even as gray-haired man and woman, at that time, I hope we can be good friends to share this memory proudly to relight the youthful and joyful emotions. If this chance never comes, I wish I were the stars in the sky and twinkling in your window, to bless you far away, as friends, to accompany you every night, sharing the sweet dreams or going through the nightmares together?

Here comes the problem: Assume the star is represented by a string sequence only including four different characters 'S', 'T', 'A' and 'R'. Of course,each character will appear many times.Your task is to write a program that will find commonalities amongst string sequces. Given a set of star sequences,Please determine the longest common subsequence that occurs in all of the sequences.

Input:

Input to this problem will begin with a line containing a single integer n indicating the number of datasets. Each dataset consists of the following components:

A single positive integer m*m* indicating the number of string sequences in this dataset. m lines each containing a single sequence consisting of 6060 characters, 2 \\leq m \\leq 102≤*m*≤10.

Output:

For each dataset in the input, output the longest subsequence common to all of the given sequences. If the longest common subsequence is less than three characters in length, display the string "No significant commonalities" instead. If multiple subsequences of the same longest length exist, output only the subsequence that comes first in alphabetical order.

#### 样例1 ####

输入：

3
    2
    SATARRASATARRASATARRASATARRASATARRASATARRASATARRASATARRASATA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    3
    SATARRASATARRASATARRASATARRASATARRASATARRASATARRASATARRASATA
    SATARTASATARTASATARTASATARTAAASSAAASSSAAAASSSSAAAAASSSSSAAAA
    SATARRASATARRASATARRASATARRAAASSAAASSSAAAASSSSAAAAASSSSSAAAA
    3
    RATRATRATRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
    ARATRATRATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AARATRATRATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

输出：

No significant commonalities
    ASATAR
    RATRATRAT

解题思路：

最长公共子序列。

#include <iostream>  
    #include <string>
    using namespace std; 
    
    string getLCSLength(string &s, string &t);
    
    int main()
    {
    	int t; scanf("%d", &t);
    	while(t--)
    	{
    		string s, b;
    		int n;  scanf("%d", &n); 
    		cin >>s;
    		for(int i=1;  i<n; i++)
    		{
    			cin >>b;
    			s=getLCSLength(s, b);
    		}
    		if(s.length()< 3)
    			printf("No significant commonalities\n");
    		else
    		cout << s<< endl;
    	}
    	return 0;
    }
    
    string getLCSLength(string &s, string &t)
    {
    	int p = s.length();
    	int q = t.length();
    
    	string **num = new string *[p];  
        for(int i=0;i<p;i++)    
        {    
            num[i] = new string[q];  
        }   
    
    	char char1 = '\0';
    	char char2 = '\0';
    
    	int len = 0;
    	string lcs = "" ;
    
    	for(int i=0; i<p; i++)
    	{
    		for (int j=0; j<t.length(); j++)
    		{
    			char1 = s.at(i);
    			char2 = t.at(j);
    			if(char1!=char2)
    			{
    				num[i][j] = "" ;
    			}
    			else
    			{
    				if (i==0||j==0)
    				{
    					num[i][j]=char1;
    				}
    				else
    				{
    					num[i][j]=num[i-1][j-1]+char1;
    				}
    				if(num[i][j].length()>len)
    				{
    					len = num[i][j].length() ;
    					lcs = num[i][j];
    				}
    				else if(num[i][j].length()==len)
    				{
    					lcs =num[i][j]; 
    					//lcs = lcs + "," + num[i][j];
    				}
    			}
    		}
    	}
    
    	for(int i=0;i<p;i++)    
        {    
            delete[] num[i]; 
        } 
    	delete[] num;
    
    	return lcs;
    }