Cod sursa(job #1770456)

Utilizator bleo16783FMI Bleotiu Cristian bleo16783 Data 4 octombrie 2016 14:19:06
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include<cstring>
#include<fstream>
#include<vector>
using namespace std;
char cos[2000010],tel[2000010];
int biju[2000010],sistem[2000010],i,k,n,m,solar;
vector<int>formatia;
int main()
{
    ifstream f("strmatch.in");
    f>>(cos+1);f>>(tel+1);f.close();
    m=strlen(cos+1)+1;n=strlen(tel+1)+1;
    biju[1]=0;
    k=0;
    for(i=2;i<m;++i)
    {
        while(k>0&&cos[k+1]!=cos[i])k=biju[k];
        if(cos[k+1]==cos[i])++k;
        biju[i]=k;
    }
    --m;
    k=0;
    for(i=1;i<n;++i)
    {
        while(k>0&&cos[k+1]!=tel[i])k=biju[k];
        if(cos[k+1]==tel[i])++k;
        sistem[i]=k;
        if(k==m)
        {
            formatia.push_back(i);
        }
    }
    solar=formatia.size();
    ofstream g("strmatch.out");
    g<<solar<<'\n';
    for(i=0;i<solar;++i)
    {
        g<<formatia[i]-m<<" ";
    }
    g.close();
    return 0;
}