Cod sursa(job #1912371)

Utilizator bleo16783FMI Bleotiu Cristian bleo16783 Data 8 martie 2017 06:33:24
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 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;
    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;
    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++]=i-n;
    }
}
int main()
{
    ifstream f("strmatch.in");
    f>>(a+1)>>(b+1);
    S(a,b);
    ofstream g("strmatch.out");
    g<<dim<<'\n';
    for(i=0;i<dim;++i)
        g<<poz[i]<<" ";
    return 0;
}