Cod sursa(job #2663847)

Utilizator metallidethantralayerIon Cojocaru metallidethantralayer Data 27 octombrie 2020 14:24:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int p[2000005];
char A[2000005],B[2000005];
vector <int> Sol;
int main()
{
    f>>A>>B;
    int n=strlen(A);
    for(int i=1,j=0; A[i];)
    {
        if(A[i]==A[j])
            p[i]=++j,i++;
        else
        {
            if(j)
                j=p[j-1];
            else
                i++;
        }
    }
    for(int i=0,j=0; B[i];)
    {
        if(B[i]==A[j])
            i++,j++;
        if(j==n)
        {
            Sol.push_back(i-j);
            j=p[j-1];
        }
        else if(B[i]!=A[j])
        {
            if(j)
                j=p[j-1];
            else
                i++;
        }
    }
    g<<Sol.size()<<'\n';
    for(int i=0;i<Sol.size()&&i<1000;i++)
        g<<Sol[i]<<' ';
    return 0;
}