Cod sursa(job #1189197)

Utilizator danalex97Dan H Alexandru danalex97 Data 21 mai 2014 19:36:06
Problema Potrivirea sirurilor Scor 52
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

ifstream F("strmatch.in");
ofstream G("strmatch.out");

const int N = 4000010;

char a[N],b[N];
int p[N],n,m;

int main()
{
    F>>a>>b;
    n = strlen(a);
    m = strlen(b);
    for (int i=n,j=0;i<n+m;++i,++j) a[i] = b[j];
    m = n;
    n = strlen(a);

    int l=1,r=0;
    p[0] = n;
    for (int i=1;i<n;++i)
    {
        p[i] = -1;
        if ( l <= i && i <= r )
        {
            p[i] = min(p[i-l],r-i+1);
        }
        if ( p[i] == r-i+1 ) l = i , r = r-i+1;
        if ( i >= r ) l = i , r = i;
        if ( i + p[i] == r && r > l ) l = i;

        if ( i == l )
        {
            while ( a[r] == a[r-l] && r < n ) ++r;
            p[i] = r-l;
        }
        if ( p[i] == -1 ) p[i] = r-l;
    }

    int co = 0;
    vector<int> ans;
    for (int i=1;i<n;++i)
        if ( p[i] >= m )
        {
            ++co;
            if ( ans.size() < 1000 )
                ans.push_back(i-m);
        }

    G<<co<<'\n';
    for (size_t i=0;i<ans.size();++i)
        G<<ans[i]<<' ';
    G<<'\n';
}