Cod sursa(job #2193707)

Utilizator lucametehauDart Monkey lucametehau Data 11 aprilie 2018 07:59:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <cstring>

using namespace std;

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

const int lmax = 1000;
const int nmax = 2000000;

int n, m;
int matches;

int sol[1 + lmax];
int lps[1 + nmax];
char txt[1 + nmax], pat[1 + nmax];

int main() {
  cin >> (pat + 1);
  cin >> (txt + 1);
  n = strlen(txt + 1);
  m = strlen(pat + 1);
  // calculez lps-ul
  int i = 0, j = 2;
  lps[1] = 0;
  while(j <= n) {
    if(pat[i + 1] == pat[j]) {
      i++;
      lps[j] = i;
      j++;
    } else {
      if(i)
        i = lps[i];
      else {
        lps[j] = 0;
        j++;
      }
    }
  }
  // fac match-urile
  i = 1;
  j = 0;
  while(i <= n) {
    if(txt[i] == pat[j + 1]) {
      i++;
      j++;
    }
    if(j == m) {
      matches++;
      if(lmax >= matches)
        sol[matches] = i - j - 1;
      j = lps[j];
    } else if(i <= n && txt[i] != pat[j + 1]) {
      if(j)
        j = lps[j];
      else
        i++;
    }
  }
  cout << matches << "\n";
  matches = min(matches, lmax);
  for(int i = 1; i <= matches; i++)
    cout << sol[i] << " ";
  return 0;
}