Cod sursa(job #2365602)

Utilizator lucametehauDart Monkey lucametehau Data 4 martie 2019 15:05:44
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

int n, m, cnt;

char a[1000005], b[1000005];
int v[1000005];
vector <int> sol;

int main() {
  cin >> (a + 1) >> (b + 1);
  n = strlen(a + 1); m = strlen(b + 1);
  int j = 0;
  for(int i = 2; i <= n; i++) {
    while(j && a[j + 1] != a[i])
      j = v[j];
    if(a[j + 1] == a[i])
      j++;
    v[i] = j;
  }
  j = 0;
  for(int i = 1; i <= m; i++) {
    while(j && a[j + 1] != b[i])
      j = v[j];
    if(a[j + 1] == b[i])
      j++;
    if(j == n) {
      cnt++;
      if(cnt <= 1000)
        sol.push_back(i - n);
    }
  }
  cout << cnt << "\n";
  for(auto i : sol)
    cout << i << " ";
  return 0;
}