Pagini recente » Cod sursa (job #1927082) | Cod sursa (job #612017) | Cod sursa (job #703855) | Cod sursa (job #1647394) | Cod sursa (job #3180252)
#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()
{
fin >> p;
fin.get();
fin >> s;
gen_prefix();
if(strlen(p) > strlen(s)){
fout << 0;
return 0;
}
kmp();
fout << sol.size() << "\n";
for(auto x : sol) fout << x << " ";
return 0;
}