POJ - 3080 Blue Jeans 字元串 暴力求最長公共連續子序列

POJ - 3080 Blue Jeans

題意：

給定一些字元串求最長公共連續子序列（子序列長度必須大于3），符合條件就輸出這個連續子序列（如果存在多個長度相同的連續子序列就輸出字典序最小的那個），否則就輸出 no significant commonalities 

思路：

按字元串長度從大到小暴力枚舉第一個字元串的所有大于3的連續子序列，并檢查其他字元串中是否含有這段連續子序列

這裡需要用到幾個函數：memcpy     strstr    strcmp   strcpy  

剛知道 puts() 中自帶換行符。。。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[11][100];
char a[100];  //存放臨時 連續最長子序列
char b[100];  //存放最長連續子序列
int main()
{
    int m,n;
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%s",s[i]);
            memset(b,0,sizeof(b)); //初始化為空字元串
        int k,flag = 0;
        for(int i=60;i>2;i--)   //子串的長度
        {

            for(int j=0;j<61-i;j++) //子串的起始點
            {
                memset(a,0,sizeof(a));  //初始化為空字元串
                memcpy(a,s[0]+j,i*sizeof(char));  // 将以s[0][j]為起點的i個字元複制給a
                for(k=1;k<n;k++)
                {
                    if( strstr(s[k],a)==NULL )  //檢驗s[k]中是否含有連續序列 a
                        break;
                }
                if(k==n)  // 全部字元串中都含有連續序列 a
                {
                    flag = 1;
                    if(b[0]=='\0')    //第一次找到長度為 i 的連續子序列  直接複制      
                        strcpy(b,a);
                    else           //如果兩連續子序列長度相同  把字典序小的複制給 b
                    {
                        if(strcmp(a,b)<0)
                            strcpy(b,a);
                    }
                }
            }
            if(flag)   //如果找到連續子序列就跳出循環
                break;
        }
        if(!flag)
            printf("no significant commonalities\n");
        else
            puts(b);  // 自帶換行符
    }
    return 0;
}