Cod sursa(job #2458035)

Utilizator Iulia25Hosu Iulia Iulia25 Data 19 septembrie 2019 12:38:27
Problema Potrivirea sirurilor Scor 4
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>

using namespace std;

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

using namespace std;

int ans, phi[205], sol[250];
string s1, s2, s;

int main()  {
  fin >> s1 >> s2;
  s = s1 + "$" + s2;
  for (int i = 0; i < s.size(); ++i)
    phi[i] = -1;
  for (int i = 1; i < s.size(); ++i)  {
    int x = i - 1;
    while (true)  {
      if (s[phi[x] + 1] == s[i] && phi[x] + 1 != i)  {
        phi[i] = phi[x] + 1;
        break;
      }
      if (x == -1)
        break;
      x = phi[x];
    }
    if (phi[i] == s1.size() - 1)  {
      ++ans;
      if (ans <= 1000)
        sol[ans] = i - phi[i] - s1.size() - 1;
    }
  }
  fout << ans << '\n';
  for (int i = 1; i <= ans; ++i)
    fout << sol[i] << ' ';
  return 0;
}