Ronzii's Blog

Just your average geek's blog

Longest Repeated Substring

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
void preCompute(string input[],string s)
{
    int n = s.length();
    for(int i=0; i<n; i++)
        input[i] = s.substr(i,n);
}
 // return the longest common prefix of first and second
string LongestCommonSubString(string first,string second)
{
    int n = min(first.length(),second.length());
    for(int i=0; i<n; i++)
        if(first[i]!=second[i])
            return first.substr(0,i);
    return first.substr(0,n);
}
// return the longest repeated string in s
string lrs(string s)
{
    int n = s.length();
    string input[n];
    // find all suffix's of s
    preCompute(input,s);
    // sort all suffix's
    sort(input, input+n);
    string lrs = "";
    // find longest repeated substring by comparing adjacent sorted suffixes
    for(int i=0; i<n-1; i++)
    {
        string x = LongestCommonSubString(input[i],input[i+1]);
        if(x.length()>lrs.length())
        {
            lrs = x;
        }
    }
    return lrs;
}
int main()
{
    string input[2] = {"banana","missisipi"};
    for(int i=0;i<2;i++)
        cout<<lrs(input[i])<<endl;
    return 0;
}

Advertisements

March 8, 2012 Posted by | C++ | , , , , , , | Leave a comment

Longest Common Substring

#include <iostream>
#include <cstring>
using namespace std;
int LongestCommonSubString(string first,string second)
{
    int n1 = first.length(), n2 = second.length(),max=0;
    if(n1==0||n2==0) return 0;
    if(n1<n2) swap(first,second);
    int *current = new int[n2];
    int *previous = new int[n2];
    for(int i=0; i<n1; i++)
    {
        for(int j=0; j<n2; j++)
        {
            if(first[i]!=second[j])
                current[j] = 0;
            else if(i==0||j==0)
                current[j] = 1;
            else
                current[j] = previous[j-1] + 1;

            if(max<current[j])
                max = current[j];
        }
        swap(previous,current);
    }
    delete [] previous;
    delete [] current;
    return max;
}
int main()
{
    cout<<LongestCommonSubString("handler","sandollar");
    return 0;
}

February 27, 2012 Posted by | C++, Dynamic Programming | , , , , , , , | Leave a comment