Pagini recente » Cod sursa (job #2665913) | Cod sursa (job #1922280) | Cod sursa (job #2560990) | Cod sursa (job #1321066) | Cod sursa (job #2151766)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define NMAX 2000002
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n, m;
int T[NMAX];
char a[NMAX], b[NMAX];
vector <int> rez;
void prefix()
{
int k = 0, i;
for(i=2; i<=n; ++i) {
while(k > 0 && a[k + 1] != a[i])
k = T[k];
if(a[k + 1] == a[i])
++k;
T[i] = k;
}
}
void KMP()
{
int k = 0, i;
for(i=1;i<=m;++i){
while(k>0 && a[k + 1] != b[i])
k = T[k];
if(a[k + 1] == b[i])
++k;
if(k==n){
rez.push_back(i - n);
k=T[k];
}
}
}
void afis()
{
int i, sz = rez.size();
g<<sz<<'\n';
for(i=0;i<rez.size() && i<1000;++i)
g<<rez[i]<<' ';
}
int main()
{
f.getline(a + 1, NMAX); //citire
f.getline(b + 1, NMAX);
n = strlen(a + 1); //dimensiuni
m = strlen(b + 1);
if(n>m) {
g<<'0';
return 0;
}
prefix(); //precalc
KMP(); //Search
afis();
return 0;
}