Cod sursa(job #2736561)

Utilizator dimi999Dimitriu Andrei dimi999 Data 3 aprilie 2021 17:12:19
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

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

int prefix[2000005];

vector <int> ans;

int main()
{
    string A, B;

    fin >> A >> B;

    A = " " + A;
    B = " " + B;

    int j = 0;

    for(int i = 1; i < A.size(); i++)
    {
        while(A[i] != A[j + 1] && j != 0)
            j = prefix[j];

        if(A[i] == A[j + 1])
            j++;

        prefix[i] = j;
    }

    j = 1;

    for(int i = 1; i < B.size(); i++)
    {
        while(B[i] != A[j] && j != 1)
            j = prefix[j - 1];

        if(B[i] == A[j])
            j++;

        if(j == A.size())
        {
            ans.push_back(i - A.size() + 1);

            j = prefix[j - 1];
        }
    }

    fout << ans.size() << '\n';

    for(int i = 0; i < min(1000, (int)ans.size()); i++)
        fout << ans[i] << ' ';

    return 0;
}