Pagini recente » Borderou de evaluare (job #507923) | Cod sursa (job #689292) | Cod sursa (job #414188) | Cod sursa (job #1670781) | Cod sursa (job #3180256)
#include <bits/stdc++.h>
#define NMAX 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[NMAX];
char p[NMAX];
int pi[NMAX];
vector <int> sol;
void gen_prefix(){
int n = strlen(p), k = 0;
pi[0] = 0;
for(int i = 1; i < n; i++){
while(k > 0 && p[i] != p[k]) k = pi[k - 1];
if(p[k] == p[i]) k++;
pi[i] = k;
}
}
void kmp(){
int n = strlen(s), m = strlen(p),k = 0;
for(int i = 0; i < n; i++){
while(k > 0 && p[k] != s[i]) k = pi[k - 1];
if(p[k] == s[i]) k++;
if(k == m) sol.push_back(i - m + 1);
}
}
int main()
{
int i;
fin >> p;
fin.get();
fin >> s;
gen_prefix();
if(strlen(p) > strlen(s)){
fout << 0;
return 0;
}
kmp();
fout << sol.size() << "\n";
for(i = 0; i < sol.size(); i++){
if(i >= 1000) break;
fout << sol[i] << " ";
}
return 0;
}