Cod sursa(job #3163457)

Utilizator Nasa1004Ema Nicole Gheorghe Nasa1004 Data 31 octombrie 2023 14:51:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <vector>

using namespace std;

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

vector < int > sol;
int main()
{

    string a, b;
    cin >> a >> b;

    int len = a.size(), cnt = 0;
    a += '#';
    a += b;

    vector < int > pi(a.size());
    pi[0] = 0;
    int k = 0;

    for(int i = 1; i < a.size(); i++)
    {
        while(k != 0 && a[k] != a[i])
            k = pi[k - 1];
        if(a[k] == a[i])
            k++;
        pi[i] = k;

        if(k == len)
        {
            cnt++;
            if(cnt <= 1000 && i > len)
                sol.push_back(i - 2 * len);
        }
    }
    cout << cnt << '\n';
    for(int i = 0; i < sol.size(); i++)
        cout << sol[i] << " ";
    /*cout << '\n';
    for(int i = 0; i < a.size(); i++)
        cout << pi[i] << " ";
    cout << '\n';
    for(int i = 0; i < a.size(); i++)
        cout << a[i] << " ";*/


    return 0;
}