Cod sursa(job #2162833)

Utilizator lflorin29Florin Laiu lflorin29 Data 12 martie 2018 14:54:02
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>
using namespace std;
const string IN("file.in");
const string OUT("file.out");
const int N = int(2e5 + 2);
int n, m, pi[N];
char a[N], b[N], aux[N];
vector<int>Kmp() {
   int size_ = n + m + 1;
   for(int i = 1; i <= n; ++i)aux[i] = a[i];
   aux[n + 1] = '#';
   for(int i = 1; i <= m; ++i)
      aux[n + 1 + i] = b[i];
   vector<int>matches;
   for(int i = 2; i <= n + m + 1; ++i) {
      int j = pi[i - 1];
      while(j > 0 && aux[j + 1] != aux[i])
         j = pi[j];
      if(aux[j + 1] == aux[i])
         ++j;
      pi[i] = j;
      if(i > n + 1 && pi[i] == n) {
         matches.push_back(i - 2 * n - 1);
      }
   }
   return matches;
}
int main() {
   ifstream cin(IN);
   ofstream cout(OUT);
   cin >> (a + 1) >> (b + 1);
   n = strlen(a + 1);
   m = strlen(b + 1);
   auto matches = Kmp();
   cout << matches.size() << '\n';
   matches.resize(min(1000, (int)matches.size()));
   for(int i : matches)
      cout << i << ' ';
}