Pagini recente » Cod sursa (job #1723509) | Cod sursa (job #661896) | Cod sursa (job #1475632) | Cod sursa (job #1890115) | Cod sursa (job #1073013)
#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 < p.size()) {
while(j >= 0 && p[i] != p[j]) j = b[j];
b[++i] = ++j;
}
}
void kmp() {
int i=0, j=0;
while(i < t.size()) {
while(j >= 0 && t[i] != p[j]) j = b[j];
i++; j++;
if(j == 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, sol.size()); i++) g<<sol[i]<<" "; g<<"\n";
return 0;
}