Cod sursa(job #2175154)

Utilizator GoogalAbabei Daniel Googal Data 16 martie 2018 15:43:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

const int NMAX = (2000000 + 100) * 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] << ' ';
  out << '\n';

  in.close();
  out.close();
  return 0;
}