Pagini recente » Cod sursa (job #2964405) | Cod sursa (job #1709967) | Cod sursa (job #1534716) | Cod sursa (job #2648393) | Cod sursa (job #3180250)
#include <bits/stdc++.h>
#define NMAX 1000005
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();
kmp();
fout << sol.size() << "\n";
for(auto x : sol) fout << x << " ";
return 0;
}