Cod sursa(job #1165430)

Utilizator andreiiiiPopa Andrei andreiiii Data 2 aprilie 2014 18:05:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <algorithm>
#include <fstream>
#include <cstring>
#include <string>

using namespace std;

const int N=2000005;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string a, b;
int Z[2*N], ap[1005];

int main()
{
    int n, m, i, k, R, L, sol=0;
    fin>>a>>b;
    n=a.size();
    a+=b;
    m=a.size();
    R=L=0;
    for(i=1;i<m;i++)
    {
        if(i>R)
        {
            L=R=i;
            for(;R<m&&a[R]==a[R-L];R++);
            Z[i]=R-L;
            R--;
        }
        else
        {
            k=i-L;
            if(Z[k]<R-i+1) Z[i]=Z[k];
            else
            {
                L=i;
                for(;R<m&&a[R]==a[R-L];R++);
                Z[i]=R-L;
                R--;
            }
        }
        if(i>=n&&Z[i]>=n)
        {
            sol++;
            if(sol<=1000) ap[sol]=i-n;
        }
    }
    fout<<sol<<"\n";
    for(i=1;i<=min(sol, 1000);i++) fout<<ap[i]<<" ";
}