Cod sursa(job #2191721)

Utilizator cella.florescuCella Florescu cella.florescu Data 3 aprilie 2018 15:45:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;

const int LIM = 1e3;
const int MAXN = 2e6;

string s, t;
int pi[MAXN + 1];
vector < int > sol;

int main()
{
    ifstream fin("strmatch.in");
    fin >> s >> t;
    fin.close();
    int k = 0, ans = 0;
    for (int i = 2; i <= (int) s.size(); ++i) {
      for (k = k; k > 0 && s[k] != s[i - 1]; k = pi[k]) {}
      pi[i] = (k += (s[k] == s[i - 1]));
    }
    k = 0;
    for (int i = 1; i <= (int) t.size(); ++i) {
      for (k = k; k > 0 && s[k] != t[i - 1]; k = pi[k]) {}
      if ((k += (s[k] == t[i - 1])) == (int) s.size()) {
        ++ans;
        if (sol.size() < LIM)
          sol.push_back(i - s.size());
      }
    }
    ofstream fout("strmatch.out");
    fout << ans << '\n';
    for (auto it : sol)
      fout << it << " ";
    fout.close();
    return 0;
}