Cod sursa(job #2370069)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 6 martie 2019 10:35:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 2000005;
int p[NMAX];
char A[NMAX];
char B[NMAX];
int v[NMAX];

int main()
{
    fin >> (A+1);
    int n=strlen(A+1);
    fin >> (B+1);
    int m=strlen(B+1);
    p[1]=0;
    int q;
    for(int i=2;i<=n;i++)
    {
        q=p[i-1];
        while(A[q+1]!=A[i] and q!=0)
        {
            q=p[q];
        }
        if(A[q+1]!=A[i]) p[i]=0;
        else p[i]=q+1;
    }
    q=0;
    int rasp=0;
    for(int i=1;i<=m;i++)
    {
        while(A[q+1]!=B[i] and q!=0)
            q=p[q];
        if(A[q+1]==B[i]) q++;
        if(q==n)
        {
            q=p[q];
            v[++rasp]=i-n;
        }
    }
    fout << rasp << '\n';
    rasp=min(rasp,1000);
    for(int i=1;i<=rasp;i++)
    {
        fout << v[i] << ' ';
    }
    return 0;
}