Cod sursa(job #2820700)

Utilizator andreiiorgulescuandrei iorgulescu andreiiorgulescu Data 21 decembrie 2021 11:40:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;

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

string a,b;
int pi[2000005],sol;
vector<int>v;

int main()
{
    in >> a >> b;
    a.push_back(' ');
    b.push_back(' ');
    int n = a.size(),m = b.size();
    for (int i = n; i >= 1; i--)
        a[i] = a[i - 1];
    for (int i = m; i >= 1; i--)
        b[i] = b[i - 1];
    int k = 0;
    pi[1] = 0;
    for (int i = 2; i <= n; i++)
    {
        while (k > 0 and a[k + 1] != a[i])
            k = pi[k];
        if (a[k + 1] == a[i])
            k++;
        pi[i] = k;
    }
    k = 0;
    for (int i = 1; i <= m; i++)
    {
        while (k > 0 and a[k + 1] != b[i])
            k = pi[k];
        if (a[k + 1] == b[i])
            k++;
        if (k == n - 1)
        {
            sol++;
            if (v.size() < 1000)
                v.push_back(i - n + 1);
        }
    }
    out << sol << '\n';
    for (int i = 0; i < v.size(); i++)
        out << v[i] << " ";
    return 0;
}