Cod sursa(job #3158578)

Utilizator donCiuarinArin Donciu donCiuarin Data 19 octombrie 2023 09:02:10
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
#define pb push_back
#define NM 2000005

using namespace std;

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

string a, b;
int lenA, lenB;
int lps[NM];
int x;
vector <int> sol;

void makeLps()
{
    int i, len = 0;
    for(i = 1; i < lenA; i++)
    {
        if(a[i] == a[len])
        {
            len++;
            lps[i] = len;
        }
        else if(len > 0)
        {
            len = lps[len - 1];
            i--;
            continue;
        }
    }
}

int main()
{
    int i = 0, j = 0;
    fin >> a >> b;

    lenA = a.size();
    lenB = b.size();
    makeLps();

    while(j < lenB)
    {
        if(a[i] == b[j])
        {
            i++;
            j++;
            if(i == lenA)
            {
                sol.pb(j - lenA);
                i = lps[i - 1];
            }
        }
        else if(i > 0)
            i = lps[i - 1];
        else
            j++;
    }

    fout << sol.size() << '\n';
    x = min(sol.size(), 1000);
    for(i = 0; i <= x; i++)
        fout << sol[i] << ' ';

    return 0;
}