Cod sursa(job #3241940)

Utilizator BogdancxTrifan Bogdan Bogdancx Data 6 septembrie 2024 13:51:59
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

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

    string a, b;

    fin >> a;
    fin >> b;

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

    vector<int>lps(n, 0);
    int i = 1, prevLPS = 0;
    while(i < n)
    {
        if(a[i] == a[prevLPS])
        {
            lps[i++] = ++prevLPS;
        }
        else if(prevLPS == 0)
        {
            lps[i++] = 0;
        }
        else
        {
            prevLPS = lps[prevLPS - 1];
        }
    }


    i = 0;
    int j = 0;
    vector<int> res;
    while(j < m)
    {
        if(a[i] == b[j])
        {
            ++i;
            ++j;
        }
        else if(i == 0)
        {
            ++j;
        }
        else
        {
            i = lps[i - 1];
        }

        if(i == n)
        {
            res.push_back(j - n);
        }
    }

    fout << res.size() << '\n';

    for(i = 0; i < min(static_cast<int>(res.size()), 1000); i++)
    {
        fout << i << ' ';
    }

    return 0;
}