Cod sursa(job #2078901)

Utilizator GoogalAbabei Daniel Googal Data 30 noiembrie 2017 11:35:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = (2000000 + 100) * 2;

string s1, s2;
int pre[1 + NMAX];
int nsol;
vector < int > sol;

void computepre(string s) {

  int i = 0; //i e la sfarsitul prefizului
  int j = 1; //j e la sfrasitul sufixului

  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()) {
      //cout << i - 1 - 2 * 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;
}