Cod sursa(job #2722204)

Utilizator Iulia25Hosu Iulia Iulia25 Data 12 martie 2021 17:29:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.65 kb
#include <fstream>

using namespace std;

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

int n, k, ans;
int pi[4000005];
string s1, s2, s;

void kmp()  {
  int p = 0;
  for (int i = 2; i <= n; ++i)  {
    while (p > 0 && s[i] != s[p + 1])
      p = pi[p];
    if (s[i] == s[p + 1])
      ++p;
    pi[i] = p;
    if (pi[i] >= k)
      ++ans;
  }
}

int main()  {
  cin >> s1 >> s2;
  k = s1.size();
  s = "#" + s1 + "#" + s2;
  n = s1.size() + s2.size() + 1;
  kmp();
  cout << ans << '\n';
  int cnt = 0;
  for (int i = k + 1; i <= n && cnt < 1000; ++i)  {
    if (pi[i] == k) {
      cout << i - k - k - 1 << ' ';
      ++cnt;
    }
  }
	return 0;
}