Cod sursa(job #3155205)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 7 octombrie 2023 17:30:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>

using namespace std;

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

const int NMAX = 2e6;

string a, b;
int LPS[2 * NMAX + 1];
int Answer[1001], ind;
int secvente;

int main()
{
    cin >> a >> b;

    int n = a.size();
    int m = b.size();

    a = a + "#" + b;

    LPS[0] = 0;
    for(int i = 1; i < a.size(); i++)
    {
        int j = LPS[i - 1];
        while(j > 0 && a[j] != a[i])
            j = LPS[j - 1];

        if(a[j] == a[i])
            j++;

        LPS[i] = j;

        if(LPS[i] == n && ind < 1000)
        {
            secvente++;
            Answer[++ind] = i - 2 * n;
        }
    }

    cout << secvente << '\n';
    for(int i = 1; i <= ind; i++)
        cout << Answer[i] << ' ';


    return 0;
}