Cod sursa(job #2878066)

Utilizator Matei_MunteanuMunteanu Matei Ioan Matei_Munteanu Data 25 martie 2022 19:19:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <bits/stdc++.h>
using namespace std;

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

string word;
string pattern;
string sir;
vector<int> poz; // pozitiile pe care apare pattern-ul
int lps[4000004];
int n; // n = lungime word
int m; // m = lungime pattern
void compute_lps_1loop()
{
    int len = 0;
    lps[0] = 0;
    int ind = 1;
    while(ind < (int)sir.size())
    {
        if (sir[ind] == sir[len])
        {
            len++;
            ind++;
            lps[ind] = len; 
        }
        else // pattern[ind] != pattern[len]
        {
            if (len > 0) // stiu ca ultimele len caractere corespund cu primele len caractere din pattern
            {            // ma uit la urmatorul sufix mai mic care e egal cu prefixul si incerc sa-l lungesc
                len = lps[len - 1];
            }
            else // len e 0 si pattern[ind] != pattern[0] => lps[ind] = 0
            {
                lps[ind] = 0;
                ind++;
            }
        }
    }
}
void kmp()
{
    lps[0] = 0;
    for (int i = 1; i < (int)sir.size(); i++)
    {
        int j = lps[i - 1];
        while (j > 0 && sir[i] != sir[j])
        {
            j = lps[j - 1];
        }
        if (sir[i] == sir[j]) // daca j e 0, atunci lps este 1, altfel daca j != 0
            j++;
        lps[i] = j;
    }
    for (int i = m + 1; i < (int)sir.size(); i++)
    {
        if (lps[i] == m)
        {
            poz.push_back(i - 2 * m);
        }
    }
}
int main() {
    fin >> pattern >> word;
    n = (int)word.size();
    m = (int)pattern.size();
    sir = pattern + '#' + word;
    kmp();
    fout << poz.size() << '\n';
    for (auto it : poz)
    {
        fout << it << ' ';
    }
    return 0;
}