Cod sursa(job #2724863)

Utilizator niculaandreiNicula Andrei Bogdan niculaandrei Data 18 martie 2021 00:09:37
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;

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

const int LEN_MAX = 2e6 + 5;
const int ANS_MAX = 1e3;

char s1[LEN_MAX], s2[LEN_MAX];
int pi[LEN_MAX], len;

vector < int > Ans;

int main()
{
    fin >> (s1 + 1) >> (s2 + 1);
    for (int i = 2; s1[i]; i++)
    {
        while (len != 0 && s1[i] != s1[len + 1])
            len = pi[len];
        if (s1[i] == s1[len + 1])
            len++;
        pi[i] = len;
    }
    len = 0;
    for (int i = 1; s2[i]; i++)
    {
        while (len != 0 && s1[len + 1] != s2[i])
            len = pi[len];
        if (s1[len + 1] == s2[i])
            len++;
        if (s1[len + 1] == 0)
        {
            if (Ans.size() <= ANS_MAX)
                Ans.push_back(i - len);
            len = pi[len];
        }
    }
    fout << Ans.size() << "\n";
    for (int i = 0; i < Ans.size(); i++)
        fout << Ans[i] << " ";
    return 0;
}