Блог пользователя runtime_error

Автор runtime_error, 11 лет назад, По-английски

hello,i have tried to compute longest common substring for more than 2 string.

i read dp solution in wikipedia.We can compute it with O(min(a,b)) memory and O(ab) time. but i don't know how to do this with 3 or more strings,when string sizes are two big-1000000; please help me! my wrong solution :

#include<iostream>
#include<string>
#include<algorithm>

#define MAX 1000000

using namespace std;

int  *m=new int [MAX];

string longest_common_substring(string s,string t)
{
    for(int i=0;i<MAX;i++)
        m[i]=0;

    int d;
    int longest=0;

    for(int i=0;i<t.size();i++)
    {
        for(int j=s.size()-1;j>=0;j--)
        {
            if(s[j]==t[i])
            {

                 m[j+1]=m[j]+1;
            }
            else m[j+1]=0;
            if(m[j+1]>longest)
            {
                longest=m[j+1];
                d=j-longest+1;
            }
        }
    }
    if(longest==0)return "";
    return s.substr(d,longest);
}


int main()
{
    string s;
    int n;
    cin>>n;
    
    cin>>s;
    for(int i=0;i<n-1;i++)
    {
        string t;
        cin>>t;
        s=longest_common_substring(s,t);
    }
    cout<<s<<endl;
    return 0;


}
  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Constraints seem pretty high for O(a * b) solution.
Not a DP approach, but the one that I know: hash every string (let's say you have K strings), so you can compare any given substring [start..end] in O(1). Now do a binary search over the length of longest common substring — say, L. Store hashes of all L-length substrings of every string you have. If some hash appeared K times (ignore repeats in same string!) — you have a candidate for an answer. This can work in something about O(K * MAX_LENGTH * log(^2)(MAX_LENGTH)).

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This problem can be solved using suffix structures, such as suffix array (O(n * log n)) or suffix automaton (O(n * k), where k is the size of the alphabet).

But after looking at your Codeforces rating it seems that you first need to master solving ad-hoc problems :).