Cod sursa(job #2080989)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 3 decembrie 2017 18:49:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>

using namespace std;

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

int const lenmax = (int) 2e6;

string s1, s2;
int pre[lenmax];
vector<int> sol;

void precompute(){
  pre[0] = 0;
  int i = 0;
  int j = 1;
  while(j < s1.size()) {
    if(s1[i] == s1[j]) {
      pre[j] = i + 1;
      i++;
      j++;
    } else {
      if(0 < i)
        i = pre[i - 1];
      else {
        pre[j] = 0;
        j++;
      }
    }
  }
  //cout<<s1<<endl;
  //for(i = 0;i < s1.size();i ++)
   //cout << pre[i];
}

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

  int i = 0;
  int j = 0;
  int nsol = 0;
  while(j < s2.size()) {
    if(s1[i] == s2[j]) {
      i++;
      j++;
      if(i == s1.size()) {
        i = pre[i-1];
        nsol++;
        if(nsol <= 1000)
          sol.push_back(j - s1.size());
      }
    } else {
        if(0 < i)
          i = pre[i - 1];
        else
          j++;
    }
  }
  out << nsol << "\n";
  for(i = 0; i < sol.size();i ++)
    out << sol[i] << " ";
  return 0;
}