Cod sursa(job #2041534)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 17 octombrie 2017 15:46:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>

using namespace std;

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

void solve(string s, vector < int > &kmp, int len) {

  for (int i = 2; i < s.size(); i ++) {

    int k = kmp[i - 1];
    if (s[i] == s[k + 1]) {
      kmp[i] = kmp[i - 1] + 1;
      continue;
    }

    while (s[k + 1] != s[i]) {
      k = kmp[k];
      if (not k) {
        break;
      }
    }

    if (s[k + 1] == s[i]) {
      kmp[i] = k + 1;
      continue;
    }

    kmp[i] = 0;
  }

  vector < int > sol(1001);
  int cnt = 0;
  int index = 0;
  for (int i = len + 1; i < s.size(); i ++) {
    if (kmp[i] == len) {
      if (index < 1000) {
        sol[++ index] = i - 1 - (2 * len);
      }
      cnt ++;
    }    
  }

  cout << cnt << '\n';
  for (int i = 1; i <= index; i ++) {
    cout << sol[i] << ' ';
  }
  cout << '\n';
}

int main(int argc, char const *argv[]) {
  
  string patt, s;
  cin >> patt >> s;

  int len = patt.size();
  s = ' ' + patt + '#' + s;

  vector < int > kmp(s.size() + 7);
  solve(s, kmp, len);
}