Cod sursa(job #1451603)

Utilizator DjokValeriu Motroi Djok Data 17 iunie 2015 20:39:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<bits/stdc++.h>
using namespace std;

int i,pref[2000005],n,m,nr,rs[1005],k;
string a,b;

int main()
{
  ifstream cin("strmatch.in");
  ofstream cout("strmatch.out");

  ios_base::sync_with_stdio(0);

  getline(cin,a); n=a.length();
  getline(cin,b); m=b.length();

  for(i=1;i<n;++i)
  {
    while(k && a[i]!=a[k]) k=pref[k-1];
    if(a[i]==a[k]) ++k;
    pref[i]=k;
  }

  for(k=i=0;i<m;++i)
  {
    while(k && b[i]!=a[k]) k=pref[k-1];
    if(a[k]==b[i]) ++k;
    if(k==n)
    {
      ++nr; k=pref[k-1];
      if(nr<=1000) rs[nr]=i-n+1;
    }
  }

  cout<<nr<<'\n'; nr=min(nr,1000);
  for(i=1;i<=nr;++i) cout<<rs[i]<<" \n"[i==nr];

 return 0;
}