Cod sursa(job #2149910)

Utilizator ade_tomiEnache Adelina ade_tomi Data 3 martie 2018 08:27:46
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <cstring>
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

vector <int> a, b, pi, sol;
string s1, s2;

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

    cin >> s1 >> s2;

    a.resize(s1.size() + 1);
    b.resize(s2.size() + 1);

    pi.resize(s1.size() + 1);

    for (int i = 0; i < s1.size(); i++) {
        a[i + 1] = s1[i];
    }

    for (int i = 0; i < s2.size(); i++) {
        b[i + 1] = s2[i];
    }

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

       if (a[k + 1] == a[i]) {
           k++;
       }

       pi[i] = k;
    }

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

        if (a[k + 1] == b[i]) {
            k++;
        }

        if (k == a.size() - 1) {
            sols ++;
            if (sol.size() <= 1000) {
                sol.push_back(i - k);
            }
            k = pi[k];
        }
    }

    cout << sols << "\n";

    for (int i = 0; i < sol.size(); i++) {
        cout << sol[i] << " " ;
    }

    return 0;
}