Cod sursa(job #1189211)

Utilizator danalex97Dan H Alexandru danalex97 Data 21 mai 2014 20:07:12
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

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

const int N = 2000010;

char a[2*N],b[N];
int Z[2*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];
    int aux = m;
    m = n;
    n = aux+m;

    int l=0,r=0;
    Z[0] = n;
    for (int i=1;i<n;++i)
    {
        Z[i] = 0;
        if ( l <= i && i <= r )
        {
            if ( Z[i-l] >= r-i+1 )
            {
                l = i;
                while ( a[r-l+1] == a[r+1] && r+1 < n ) ++r;
                Z[i] = r-l+1;
            }
            else
                Z[i] = Z[i-l];
        }
        else
            if ( a[i] == a[0] )
            {
                l = r = i;
                while ( a[r-l+1] == a[r+1] && r+1 < n ) ++r;
                Z[i] = r-l+1;
            }
    }

    int co = 0;
    vector<int> ans;
    for (int i=1;i<n;++i)
        if ( Z[i] >= m && 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';
}