Cod sursa(job #1974990)

Utilizator MotoAMotoi Alexandru MotoA Data 29 aprilie 2017 17:31:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <vector>
#include <iterator>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
//#define tr(a,i) for(typeof(a.begin())i=a.begin();i!=a.end();i++)
#define NMAX 2000002
typedef vector <int> vi;
string a,b;
int n,m,nr,p[NMAX];
vi sol;

void prefix(string s,int n){
 p[1]=0;
 int k=0;
 for(int i=2;i<=n;i++){
  while(k && s[i]!=s[k+1])
    k=p[k];
  if(s[i]==s[k+1])
    k++;
  p[i]=k;
 }
}

void kmp(string &a,int n,string &b,int m){
 if(n>m)return;
 if(n==m){if(a.compare(b)==0){g<<"1\n";return;}
   else return;}
 prefix(a,n);
 int k=0;
 for(int i=1;i<=m;i++){
  while(k && a[k+1]!=b[i])
   k=p[k];
   if(a[k+1]==b[i])k++;
   if(k==n){
   k=p[n];
   ++nr;
   if(nr<=1000)
   sol.push_back(i-n);
    }
  }
}


int main(){
 getline(f,a);
 getline(f,b);
 a.insert(a.begin(),' ');
 b.insert(b.begin(),' ');
 kmp(a,a.size()-1,b,b.size()-1);
 g<<nr<<'\n';
 if(nr>1000)sol.resize(1000);
 for(vector <int>::iterator it=sol.begin();it!=sol.end();it++)
 g<<*it<<' ';
}