Cod sursa(job #2899182)

Utilizator AlexNeaguAlexandru AlexNeagu Data 8 mai 2022 01:56:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
	
#include <fstream>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int lps[2000005], l = 0;
vector < int > v;
void compute_lps(string a) {
  int len = 0, i = 1, n = a.size();
  while(i < n) {
    if (a[i] == a[len]) {
      len++;
      lps[i] = len;
      i++;
    }
    else {
      if (len != 0) {
        len = lps[len - 1];
      }
      else {
        lps[i] = 0;
        i++;
      }
    }
  }
}
void kmp(string a, string b) {
  int i = 0, j = 0, n = a.size(), m = b.size();
  while(i < n) {
    if (a[i] == b[j]) {
      i++, j++;
    }
    if (j == m) {
      l++;
      if(v.size() < 1000) v.push_back(i - j);
      j = lps[j - 1];
    }
    else if (i < n && a[i] != b[j]) {
      if (j != 0) j = lps[j - 1];
      else i++;
    }
  }
}
int main() {
  string s, pat;
  in >> pat >> s;
  compute_lps(pat);
  kmp(s, pat);
  out << l << "\n";
  for (auto it : v) out << it << " ";
  return 0;
}