Cod sursa(job #2687390)

Utilizator TheGodYatoBUGNAR CATALIN TheGodYato Data 19 decembrie 2020 23:14:16
Problema Potrivirea sirurilor Scor 52
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#define Nmax 2000005
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector <int>v;
int main()
{
    char a[Nmax],b[Nmax];
    fin>>a>>b;
    int n=strlen(a),m=strlen(b),i,j,k=0,pi[Nmax];
    pi[1]=0;
    for(i=2;i<=n;++i)
    {
        while(a[i-1]!=a[k] && k)k=pi[k];
        if(a[i-1]==a[k])++k;
        pi[i]=k;
    }
    for(i=1;i<=m;++i)
    {
        while(b[i-1]!=a[k] && k)k=pi[k];
        if(b[i-1]==a[k])++k;
        if(k==n)v.push_back(i-k);
    }
    fout<<v.size()<<'\n';
    while(v.size()>1000)v.pop_back();
    for(auto i : v)
        fout<<i<<' ';
    return 0;
}