Cod sursa(job #2547703)

Utilizator Alex2421Nedelcu Alexandru Alex2421 Data 15 februarie 2020 16:40:32
Problema Potrivirea sirurilor Scor 4
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;

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

int const lim=2000001;
char a[lim],b[lim];
int pi[lim],d[lim];
vector < int> c;

int main()
{
    in>>a>>b;

    int k=0 , n=strlen(a);
    pi[1]=0;

    for(int i=2;i<=n;i++)
    {
        while(k>0 && a[i-1]!=a[k])
            k=pi[k-1];
        if(a[i-1]==a[k])
            k++;
        pi[i-1]=k;
    }

    k=0;
    int m=strlen(b);

    for(int i=1;i<=m;i++)
    {
        while(k>0 && b[i-1]!=a[k])
            k=d[k-1];
        if(b[i-1]==a[k])
            k++;
        d[i-1]=k;
        if(k==n) c.push_back(i-k);
    }

    out<<c.size()<<'\n';
  if(c.size()<=1000)  for(int i=0;i<c.size();i++)
        out<<c[i]<<" ";
        else
            for(int i=0;i<=1000;i++)
            out<<c[i]<<" ";

}