Cod sursa(job #2312921)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 5 ianuarie 2019 19:32:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
// By Stefan Radu

#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <string>
#include <cctype>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

using namespace std;

#define sz(x) (int)(x).size ()

typedef pair < int, int > pii;
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

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

int main () {

 string a, b;
 cin >> b >> a;

 a = '#' + b + '#' + a;

 vector < int > kmp (sz (a) + 1);

 int ans = 0, k = 0;

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

   while (k) {
      if (a[i] == a[k + 1]) {
          break;
      }

      k = kmp[k];
   }

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

   if (kmp[i] == sz (b)) {
      ++ ans;
   }
 }

 cout << ans << '\n';

  ans = 0;
  for (int i = 1; i < sz (kmp); ++ i) {
      if (kmp[i] == sz (b)) {
          ++ ans;
          cout << i - 2 * sz (b) - 1 << ' ';
      }

      if (ans == 1000) break;
  }
}