poj 3080 여 개의 문자열 에서 가장 긴 공공 하위 문자열 kmp 를 찾 습 니 다.

http://poj.org/problem?id=3080
kmp 는 개선 판 의 폭력 문자열 이 일치 하고 두 가지 개념 을 명 확 히 합 니 다.하위 문자열 과 하위 서열 은 반드시 연속 적 이 어야 합 니 다.하위 서열 이 일정 하지 않 습 니 다.dp 는 가장 긴 공공 하위 서열 이 문제 입 니 다.여기 서 구 하 는 것 은 공공 하위 문자열 입 니 다.
kmp 알고리즘 은 가장 중요 한 것 은 next 배열 이 고 kmp 일치 함수 입 니 다.
이 문 제 는 10 개 이상 의 문자열 을 입력 하지 않 고 각 문자열 의 길이 가 60 을 넘 지 않 는 다 는 뜻 이다.그리고 가장 긴 공공 문자열 을 찾 아 라.여러 개의 하위 문자열 길이 가 같 으 면 사전 순서 가 가장 작고 공공 하위 문자열 의 길이 가 3 보다 작 으 면 출력 하지 않 는 다(DNA 이기 때문이다)는 뜻 이다.
사고방식:첫 번 째 문자열 을 기준 으로 모든 문자열 을 찾아내 고 substr 를 사용 한 다음 에 다시 순환 합 니 다.이 문자열 들 은 각각 남 은 문자열 에 kmp 를 매 칭 하기 때문에 모두 3 중 순환 입 니 다.

#include
using namespace std;

string data[15];
int next[65];

void Get_next(string s,int len)
{
    next[0]=-1;
    int k=-1;
    int i;
    for(i=1;iwhile(k>-1&&s[k+1]!=s[i])
        {
            k=next[k];
            //cout<
        }
        if(s[k+1]==s[i])
            k++;
        next[i]=k;
    }

}

bool kmp(string ptr,int plen,string str,int slen)
{
    int k=-1;
    for(int i=0;iwhile(k>-1&&str[k+1]!=ptr[i])
            k=next[k];
        if(str[k+1]==ptr[i])
            k++;
        if(k==slen-1)
            return true;
    }
    return 0;
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int m;
        scanf("%d",&m);
        int i,j,k;
        for(i=0;icin>>data[i];
        /*Get_next(data[0],data[0].size());
        for(i=0;i
        string ans="";
        for(i=1;i<=data[0].size();i++)
        {
            for(j=0;j<=data[0].size()-i;j++)
            {
                string op=data[0].substr(j,i);
                Get_next(op,op.size());
                bool flag=0;
                for(k=1;kif(!kmp(data[k],data[k].size(),op,op.size()))
                        flag=1;
                }
                if(!flag)
                {
                    if(ans.size()else
                    if(ans.size()==op.size())
                    ans=min(ans,op);
                }
            }
        }
        if(ans.size()<3)
        cout<<"no significant commonalities"<else
        cout<return 0;
}

☝이것 은 지저분 하고 정확 한 결 과 를 얻 지 못 하 는 코드 입 니 다.