Cod sursa(job #2491559)

Utilizator AlexPascu007Pascu Ionut Alexandru AlexPascu007 Data 12 noiembrie 2019 19:17:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>
#define DIM 2000010
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,m,k,q,i,p[DIM],s[1010];
char A[DIM],B[DIM];
int main() {
    fin>>(A+1)>>(B+1);
    n=strlen(A+1), m=strlen(B+1);
    for (i=2;i<=n;i++) {
        while (k!=0&&A[k+1]!=A[i])
            k=p[k];
        if (A[k+1]==A[i])
            k++;
        p[i]=k;
    }
    k=0;
    for (i=1;i<=m;i++) {
        while (q!=0&&B[i]!=A[q+1])
            q=p[q];
        if (A[q+1]==B[i])
            q++;
        if (q==n) {
            k++;
            if (k<=1000)
                s[k]=i-n;
            q=p[q];
        }
    }
    fout<<k<<"\n";
    k=min(k,1000);
    for (i=1;i<=k;i++)
        fout<<s[i]<<" ";
    return 0;
}