Cod sursa(job #1981187)

Utilizator MKLOLDragos Ristache MKLOL Data 15 mai 2017 05:15:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define FOR(i, to) for (int i = 0; i < (to); ++i)
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pair<int, int> > vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
#define Nmax 2101010
int nx[Nmax];
string s1,s2;
vi ret;
void make() {
  int k = -1; nx[0] = -1;
  for(int i=1;i<sz(s1);++i) {
    while(k >= 0 && s1[k+1] != s1[i]) k = nx[k];
    if(s1[k+1] == s1[i]) ++k; nx[i] = k;
  }
}
void match() {
  int k=-1;
  for(int i=0;i<sz(s2);++i) {
    while(k >= 0 && s1[k+1] != s2[i]) k = nx[k];
    if(s1[k+1] == s2[i]) ++k; if(k==sz(s1)-1) { k = nx[k]; ret.pb(i+1 - sz(s1));} 
  }
}

int main() {
  ifstream fin("strmatch.in");
  ofstream fout("strmatch.out");
  cin.sync_with_stdio(false);
  fin >> s1 >> s2;
  make();
  match();
  fout << sz(ret) << endl;
  FOR(i,min(1000,sz(ret))) {
    fout << ret[i] << " ";
  }
}