Cod sursa(job #2383776)

Utilizator PetyAlexandru Peticaru Pety Data 19 martie 2019 19:43:59
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include<bits/stdc++.h>
using namespace std;

ifstream fin ("a.in");
ofstream fout ("a.out");

string a, b;
int lps[2000002];
vector<int>ans;

int main()
{
  fin >> a >> b;
  int n = a.size(), m = b.size();
  int l = 0, i = 1;
  lps[0] = 0;
  while (i < n) {
    if (a[i] == a[l]) {
      l++;
      lps[i] = l;
      i++;
    }
    else {
      if (l != 0)
        l = lps[l - 1];
      else {
        lps[i] = 0;
        i++;
      }
    }
  }
  i = 0;
  int j = 0;
  while (i < m) {
    if (a[j] == b[i]) {
      i++;
      j++;
    }
    if (j == n) {
      ans.push_back(i - j);
      j = lps[j - 1];
    }
    else if (i < m && a[j] != b[i]) {
      if (j != 0)
        j = lps[j - 1];
      else
        i++;
    }
  }
  fout << ans.size() << "\n";
  for (int i = 0; i < ans.size(); i++)
    fout << ans[i] << " ";
  return 0;
}