Pagini recente » Cod sursa (job #1927330) | Cod sursa (job #486928) | Cod sursa (job #420116) | Cod sursa (job #977219) | Cod sursa (job #1700292)
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
const int N = 2 + 2e6;
char text[N], patt[N];
vector<int> sol;
int pi[N];
void kmp(char* text, char* patt){
pi[0] = -1; pi[1] = 0;
for (int i = 2, k = 0; patt[i]; i++, k++){
while ( k >= 0 && patt[k + 1] != patt[i] )
k = pi[k];
pi[i] = k + 1;
}
for (int i = 1, k = 0; text[i]; i++, k++){
while ( k >= 0 && patt[k + 1] != text[i] )
k = pi[k];
if ( !patt[k + 2] )
sol.push_back(i - k);
}
}
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
cin >> (patt + 1) >> (text + 1);
kmp(text, patt);
cout << sol.size() << '\n';
for (int i = 0; i < sol.size() && i < 1000; i++)
cout << sol[i] - 1 << ' ';
cout << '\n';
return 0;
}