Cod sursa(job #2353502)

Utilizator serbandonceanSerban Doncean serbandoncean Data 24 februarie 2019 12:43:01
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
#define DMAX 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,m;
char a[DMAX],b[DMAX];
int poz[DMAX];
int k,nrpotr,unde[1003];

int main()
{int i;
    fin>>a+1;
    fin>>b+1;
    n=strlen(a+1);
    m=strlen(b+1);
    poz[1]=0;
    k=0;
    //construiecte prefix
    for(i=2;i<=n;i++)
        {while(k>0&&a[k+1]!=a[i])
            k=poz[k];
        if(a[i]==a[k+1])
            k=k+1;
        poz[i]=k;
        }
    //caomparam
    if(a[1]==b[1])
        k=1;
    else
        k=0;
    for(i=2;i<=m;i++)
    {
        while(k>0&&a[k+1]!=b[i])
            k=poz[k];
        if(a[k+1]==b[i])
            k=k+1;
        if(k==n)
        {nrpotr++;
        if(nrpotr<=1000)
            unde[nrpotr]=i-n;
        }
    }
    fout<<nrpotr<<'\n';
    for(i=1;i<=nrpotr;i++)
        fout<<unde[i]<<' ';
    fout<<'\n';
        return 0;
}