Cod sursa(job #1492111)

Utilizator ELHoriaHoria Cretescu ELHoria Data 27 septembrie 2015 03:15:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <string>
#include <vector> 

using namespace std;
 
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
 
void kmp(const string &s,const string &t) {
    vector<int> a(s.size()), v(1000);
    size_t k = 0, i, match = 0;
    for(i = 1;i < s.size();++i) {
        while(k > 0 && s[i] != s[k]) 
        k = a[k - 1]; 
        if(s[i] == s[k]) k++; 
        a[i] = k;
    }
    k = 0;
    for(i = 0;i < t.size();++i) {
        while(k > 0 && t[i] != s[k]) k = a[k-1]; 
        if(t[i] == s[k]) k++; 
        if(k == s.size()) {   
          if(match < 1000) v[match++] =  i + 1 - s.size();
          else match++;
          k = a[k-1];
        }
    }
    fout << match << '\n';
    match = min(match, (size_t)1000);
    for(i = 0;i < match;++i)
        fout << v[i] <<" ";
}
 
int main()
{
    string a ,b;
    fin >> a >> b;
    kmp(a, b); 
    return 0;
}