Cod sursa(job #2156337)

Utilizator andreiiiiPopa Andrei andreiiii Data 8 martie 2018 17:39:56
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;

vector<int> Zfunction(string s) {
    int n = s.size();
    vector<int> z(n);
    int L = 0, R = 0;
    for (int i = 1; i < n; i++) {
      if (i > R) {
        L = R = i;
        while (R < n && s[R-L] == s[R]) R++;
        z[i] = R-L; R--;
      } else {
        int k = i-L;
        if (z[k] < R-i+1) z[i] = z[k];
        else {
          L = i;
          while (R < n && s[R-L] == s[R]) R++;
          z[i] = R-L; R--;
        }
      }
    }
    return z;
}


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

    string a, b;
    fin >> a >> b;

    b = a + "$" + b;
    vector<int> z = Zfunction(b);
    vector<int> ap;
    for (int i = 1; i < (int) b.size(); ++i) {
        if (z[i] == a.size()) {
            ap.push_back(i - a.size());
        }
    }
    fout << ap.size() << '\n';
    ap.resize(min(ap.size(), 1000LU));
    for (int x: ap) {
        fout << x - 1 << ' ';
    }
    fout << '\n';
}