Cod sursa(job #2288896)

Utilizator MDiana15Diana M MDiana15 Data 24 noiembrie 2018 09:03:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char c[2000010],a[2000010];
int p[2000010],sol[1005];
int i,j,k,nr,n,m,l;
int main()
{
    f.getline(c+1,2000010);
    f.getline(a+1,2000010);
    n=strlen(c+1);
    m=strlen(a+1);
    k=0;
    for(i=2;i<=n;i++)
    {
        for(;k!=0&&c[k+1]!=c[i];)k=p[k];
        if(c[k+1]==c[i])k++;
        p[i]=k;
    }
    k=0;
    for(i=1;i<=m;i++)
    {
        for(;k!=0&&c[k+1]!=a[i];)k=p[k];
        if(c[k+1]==a[i])k++;
        if(k==n){nr++;if(l<=1000){sol[++l]=i-n;}}
    }
    g<<nr<<'\n';
  for(i=1;i<=l;i++)g<<sol[i]<<" ";
    return 0;
}