Cod sursa(job #1920525)

Utilizator bleo16783FMI Bleotiu Cristian bleo16783 Data 10 martie 2017 05:09:54
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include<fstream>
#include<cstring>
using namespace std;
#define N 2000200
int n,m,i,j,phi[N],poz[1010],dim,k;
char a[N],b[N];
void phi_compute(char v[])
{
    int len=strlen(v+1);
    phi[1]=0;
    k=0;++len;
    for(int i=2;i<len;++i)
    {
        while(v[i]!=v[ k+1 ] && k )
            k=phi[k];
        if(v[k+1]==v[i])
            ++k;
        phi[i]=k;
    }
}
void S(char v[],char w[])
{
    phi_compute(v);
    n=strlen(v+1);m=strlen(w+1);
    dim=0;k=0;
    ++m;--n;
    for(int i=1;i<m;++i)
    {
        while(k && v[k+1]!=w[i])
            k=phi[k];
        if(v[k+1]==w[i])
            ++k;
        if(k>n && dim++<1000)
            poz[dim-1]=i-n+1;
    }
}
int main()
{
    ifstream f("strmatch.in");
    f>>(a+1)>>(b+1);
    S(a,b);
    ofstream g("strmatch.out");
    g<<dim<<'\n';
    dim=min(1000,dim);
    for(i=0;i<dim;++i)
        g<<poz[i]<<' ';
    return 0;
}