Cod sursa(job #1579179)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 24 ianuarie 2016 14:55:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;
char A[2000005],B[2000005];
int P[2000005],N,M,cnt;
vector<int> poz;

void Prefix()
{
    int q = 0;
    for(int i = 2; i <= N; ++i)
    {
        while(q && A[i] != A[q + 1])
            q = P[q];
        q += A[i] == A[q + 1];
        P[i] = q;
    }
}

void Match_KMP()
{
    int q = 0;
    for(int i = 1; i <= M; ++i)
    {
        while(q && B[i] != A[q + 1])
            q = P[q];
        q += B[i] == A[q+1];
        if(q == N)
        {
            ++cnt;
            q = P[q];
            if(poz.size() < 1000)
                poz.push_back(i-N);
        }
    }
}

void Read()
{
    scanf("%s%s",A+1,B+1);
    A[0] = B[0] = '#';
    N = strlen(A+1);
    M = strlen(B+1);
}

void Print()
{
    printf("%d\n",cnt);
    for(auto it : poz)
        printf("%d ",it);
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    Read();
    Prefix();
    Match_KMP();
    Print();

    return 0;
}