Pagini recente » Cod sursa (job #2063538) | Cod sursa (job #2139973) | Cod sursa (job #1186950) | Cod sursa (job #3132132) | Cod sursa (job #1349231)
#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
int t[2000010];
using namespace std;
int main()
{
string pat;
string s;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
t[0] = -1;
t[1] = 0;
int i, j, n;
cin >> pat;
cin >> s;
n = pat.length();
i = 2; j = 0;
while(i < n) {
if(pat[i-1] == pat[j]) {
++j;
t[i] = j;
++i;
} else if(j > 0) {
j = t[j];
} else {
t[i] = 0;
++i;
}
++i;
}
int m = s.length();
vector<int> lame;
i = 0;
j = 0;
while(i + j < m) {
if(s[i + j] == pat[j]) {
if(j == n - 1) {
lame.push_back(i);
i += j - t[j];
j = t[j];
}
++j;
} else {
if(t[j] > -1) {
i += j - t[j];
j = t[j];
} else {
j = 0;
++i;
}
}
}
printf("%d\n", lame.size());
for(int i = 0 ; i < lame.size() ; ++i) {
printf("%d ", lame[i]);
}
return 0;
}