Cod sursa(job #1862540)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 30 ianuarie 2017 01:10:50
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<fstream>
#include<vector>
#include<string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char a[2000001], b[2000001];
int prev_pos[2000001];
vector<int> indices;

int main() {
  fin >> a >> b;

  int i, j;
  // Precompute positions of where to restart matching in case of a mismatch
  for (i = 1, j = 0; a[i] != '\0'; i++) {
    if (a[i] == a[j]) {
      prev_pos[i] = ++j;
    } else {
      while (j != 0 && a[i] != a[j]) {
        j = prev_pos[j - 1];
      }
      if (a[i] == a[j]) {
        j++;
      }
      prev_pos[i] = j;
    }
  }


  int pattern_length = strlen(a);
  for (i = j = 0; b[i] != '\0'; i++) {
    while (j != 0 && b[i] != a[j]) {
      j = prev_pos[j - 1];
    }

    if (b[i] == a[j]) {
      j++;
    }

    if (a[j] == '\0') {
      indices.push_back(i - pattern_length + 1);
      j = prev_pos[j - 1];
    }
  }

  fout << indices.size() << "\n";
  for (i = 0; i < min(1000, indices.size()); i++) {
    fout << indices[i] << " ";
  }
  
  return 0;
}