Cod sursa(job #2700285)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 27 ianuarie 2021 09:27:20
Problema Potrivirea sirurilor Scor 86
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
#define LMAX 2000002
using namespace std;

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

char A[LMAX], B[LMAX];
char C[LMAX+LMAX];
int Z[LMAX+LMAX],cnt;

int main()
{
    in.getline(A,LMAX);
    in.getline(B,LMAX);
    int n=strlen(A),m=strlen(B);
    if(n>m)
    {
        cout<<"0";
        return 0;
    }
    strcpy(C,A);
    strcat(C,"+");
    strcat(C,B);
    int L=0,R=0;
    for(int i=1;i<n+m+1;i++)
    {
        if(i>R)
        {
            L=i;
            R=i;
            while(R<n+m+1 && C[R]==C[R-i])
                R++;
            R--;
            Z[i]=R-L+1;
        }
        else
        {
            int k=i-L;
            if(R-i+1>Z[k])
                Z[i]=Z[k];
            else
            {
                L=i;
                while(R<n+m+1 && C[R]==C[R-i])
                    R++;
                R--;
                Z[i]=R-L+1;
            }
        }
        if(Z[i]==n)
            cnt++;
    }
    out<<cnt<<'\n';
    int ok=1;
    for(int i=n+1;i<n+m+1 && ok<=1000;i++)
        if(Z[i]==n){
            out<<i-n-1<<' ';
            ok++;
        }
    return 0;
}