Cod sursa(job #2883969)

Utilizator valentinchipuc123Valentin Chipuc valentinchipuc123 Data 2 aprilie 2022 01:31:28
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>

using namespace std;

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

int N,M,pi[2000005];
int pos[1024];
string A,B;

void automate()
{
    int i,poz=0;
    pi[1]=0;

    for(int i=2; i<=M; i++)
    {
        while(poz&&A[i]!=A[poz+1]) poz=pi[poz];
        if(A[poz+1]==A[i]) poz++;
        pi[i]=poz;
    }
}

int main()
{
    f>>A>>B;
    M=A.size();
    N=B.size();
    A=" "+A;
    B=" "+B;

    automate();

    int q=0,n=0;
    vector<int>elem;

    for (int i = 1; i <= N; ++i)
    {
        while (q && A[q+1] != B[i])
            q = pi[q];
        if (A[q+1] == B[i])
            ++q;
        if (q == M)
        {
            q = pi[M];
            n++;
            if (n <= 1000)
                elem.push_back(i-M);
        }
    }

    for (int i = 1; i <= N; ++i)
    {
        while (q && A[q+1] != B[i])
            q = pi[q];
        if (A[q+1] == B[i])
            ++q;
        if (q == M)
        {
            q = pi[M];
            ++n;
            if (n <= 1000)
                pos[n] = i-M;
        }
    }

    printf("%d\n", n);
    for (int i = 1; i <= min(n, 1000); ++i)
        printf("%d ", pos[i]);
    printf("\n");


    return 0;
}