Cod sursa(job #2374380)

Utilizator GoogalAbabei Daniel Googal Data 7 martie 2019 18:16:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

const int NMAX = 2 * (2 * 1e6 + 1e2);

int nsol;
int pref[1 + NMAX];

string s1;
string s2;

vector < int > res;

void precompute(string s) {
  int i = 0;
  int j = 1;

  pref[0] = 0;
  while(j < s.size()) {
    if(s[i] == s[j]) {
      pref[j] = i + 1;
      i++;
      j++;
    } else {
      if(i > 0)
        i = pref[i - 1];
      else {
        pref[j] = 0;
        j++;
      }
    }
  }
}

int main()
{
  in >> s1 >> s2;

  precompute(s1 + '*' + s2);

  for(int i = s1.size(); i < s1.size() + s2.size() + 1; i++) {
    if(pref[i] == s1.size()) {
      nsol++;

      if(nsol <= 1000) {
        res.push_back(i - 2 * s1.size());
      }
    }
  }

  out << nsol << '\n';

  for(int i = 0; i < res.size(); i++)
    out << res[i] << ' ';

  out << '\n';

  in.close();
  out.close();

  return 0;
}