Cod sursa(job #3219877)

Utilizator BogaBossBogdan Iurian BogaBoss Data 1 aprilie 2024 17:53:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
string s,p;
int lps[2000006];
vector<int> v;
int main()
{
    fi>>p>>s;
    lps[0] = 0;
    int i = 1,k = 0;
    while(i<p.size()) {
        if (p[i]==p[k]) {
            k++;
            lps[i] = k;
            i++;
        } else {
            if (k!=0) {
                k = lps[k-1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    k = 0;
    i = 0;
    int rez = 0;
    while(i<s.size()) {
            if (s[i]==p[k]) {
                i++;
                k++;
                if (k==p.size()) {
                    rez++;
                    if (rez<=1000)
                        v.push_back(i-k);
                    k = lps[k-1];
                }
            } else {
                if (k!=0) {
                    k = lps[k-1];
                } else {
                    i++;
                }
            }
    }
    fo<<rez<<'\n';
    for (auto el : v)
        fo<<el<<' ';
    return 0;
}