Cod sursa(job #2105859)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 14 ianuarie 2018 14:28:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <vector>
#include <string>

using namespace std;

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

void Solve (string s, int l) {

  int sz = (int) s.size (), ans = 0;
  vector < int > kmp (sz), sol;
  sol.reserve (1000);

  for (int i = 2; i < sz; ++ i) {

    int k = kmp[i - 1];
    while (k != 0) {
      if (s[k + 1] == s[i]) {
        break;
      }
      k = kmp[k];
    }
  
    s[k + 1] == s[i] ? (kmp[i] = k + 1) : (kmp[i] = k);
    if (kmp[i] == l) {
      ++ ans;
      if (sol.size () < 1000) {
        sol.emplace_back (i - (2 * l) - 1);
      }
    }
  }
  
  cout << ans << '\n';
  for (auto x : sol) {
    cout << x << ' ';
  }
  cout << '\n';
}

int main () {
  ios::sync_with_stdio (false);
  
  string s1, s2;
  cin >> s1 >> s2;
  s2 = ' ' + s1 + '#' + s2;
  
  Solve (s2, (int) s1.size ());
}