Pagini recente » Cod sursa (job #2178945) | Cod sursa (job #3133735) | Cod sursa (job #2946447) | Cod sursa (job #99398) | Cod sursa (job #2808514)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int N = 2000005;
char text[N], pattern[N];
int lps[N], ans[1005], cnt;
void buildLPS(int m){
int len = 0;
int i = 1;
while(i < m){
if(pattern[i] == pattern[len]){
len++;
lps[i++] = len;
}
else{
if(len != 0){
len = lps[len - 1];
}
else{
lps[i++] = 0;
}
}
}
}
void KMP(){
int m = strlen(pattern);
int n = strlen(text);
int i = 0, j = 0;
buildLPS(m);
while(i < n){
if(pattern[j] == text[i]){
i++;
j++;
}
if(j == m){
cnt++;
if(cnt <= 1000){
ans[cnt] = i - j;
}
j = lps[j - 1];
}
else if(i < n and pattern[j] != text[i]){
if(j != 0){
j = lps[j - 1];
}
else{
i++;
}
}
}
}
int main()
{
in.get(pattern, N); in.get();
in.get(text, N);
KMP();
out << cnt << '\n';
cnt = min(cnt, 1000);
for(int i = 1; i <= cnt; i++){
out << ans[i] << " ";
}
return 0;
}