Cod sursa(job #2191719)

Utilizator cella.florescuCella Florescu cella.florescu Data 3 aprilie 2018 15:42:56
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;

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

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