Cod sursa(job #2344844)

Utilizator GoogalAbabei Daniel Googal Data 15 februarie 2019 17:58:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

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

int nsol;
int pre[1 + NMAX];

string s1, s2;

vector < int > sol;

void computepre(string s) {

  int i = 0;
  int j = 1;

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

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

  computepre(s1 + '*' + s2);

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

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

  out << nsol << '\n';

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

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

  return 0;
}