Pagini recente » Cod sursa (job #3234840) | Cod sursa (job #2854712) | Cod sursa (job #1953853) | Cod sursa (job #427816) | Cod sursa (job #1073015)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define nmax 2000005
using namespace std;
string p, t;
vector <int> sol;
int b[nmax];
void preprocess() {
int i=0, j=-1;
b[0] = -1;
while(i < int(p.size())) {
while(j >= 0 && p[i] != p[j]) j = b[j];
b[++i] = ++j;
}
}
void kmp() {
int i=0, j=0;
while(i < int(t.size())) {
while(j >= 0 && t[i] != p[j]) j = b[j];
i++; j++;
if(j == int(p.size())) {
sol.push_back(i-j);
j = b[j];
}
}
}
int main() {
ifstream f("strmatch.in");
ofstream g("strmatch.out");
getline(f, p);
getline(f, t);
preprocess();
kmp();
g<<sol.size()<<"\n";
for(int i=0; i<min(1000, int(sol.size())); i++) g<<sol[i]<<" "; g<<"\n";
return 0;
}