Cod sursa(job #1274021)

Utilizator juniorOvidiu Rosca junior Data 23 noiembrie 2014 05:39:04
Problema Potrivirea sirurilor Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <fstream>
#include <iostream>

using namespace std;

string p, t; // modelul care se cauta, textul in care se cauta
int lpref[20], s[20], lp, i, ns; // lungimile prefixelor
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

void kmp_table (string p) {
  int i = 0, j = 0;
  char c = '\0';
  lpref[0] = -1; // !! ca sa se avanseze in t folosind formula (*)
  while (i <= lp - 1) {
    if (p[i] == c) {
      lpref[i + 1] = j + 1; j++; i++;
    }
    else
      if (j > 0)
        j = lpref[j];
      else {
        lpref[i + 1] = 0; j = 0; i++;
      }
    c = p[j];
  }
}

int kmp_search (string p, string t) {
  int it = 0, ip = 0;
  int ls = t.size(), lp = p.size();
  while (it + ip <= ls - 1) { // nu t-a terminat nici unul dintre siruri
    //cout << "t[it + ip] = " << t[it + ip] << ' ' << "p[ip] = " << p[ip] << '\n';
    if (t[it + ip] == p[ip]) { // caracterele se potrivesc
      ip++;             // trecem sa comparam urmatorul caracter
      //cout << "ip = " << ip << '\n';
    }
    else {
      it += ip - lpref[ip]; // noua pozitie in sirul t (*)
      //cout << "it = " << it << '\n';
      if (ip > 0) {
        ip = lpref[ip];
        //cout << "ip = " << ip << '\n';
      }
    }
    if (ip == lp) {
      //cout << "gasit la " << it << ' ' << '\n';
      ns++;
      if (ns <= 1000)
        s[ns] = it;
    }
  }
  if (p[ip])
    return -1;
  else
    return it;
}

int main () {
  //p = "abcaabcabd"; lp = p.size();
  p = "ABA"; lp = p.size();
  t = "CABBCABABAB";
  fin >> p >> t;
  kmp_table(p);
/*
  for (i = 1; i <= lp; i++)
    cout << lpref[i];
  cout << '\n';
*/
  kmp_search(p, t);
  fout << ns << '\n';
  for (i = 1; i <= min(ns, 1000); i++)
    fout << s[i] << ' ';
}