Pagini recente » Cod sursa (job #2869430) | Cod sursa (job #1186772) | cluj.love.icrisop | Cod sursa (job #1007995) | Cod sursa (job #1716588)
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
#define DMAX 2000002
using namespace std;
vector<int> Sol, T;
char W[DMAX], S[DMAX];
int sizeW, sizeS;
void Read();
void KMP();
void Compute_Prefix();
void Write();
int main()
{
Read();
KMP();
Write();
return 0;
}
void Compute_Prefix() {
T.assign(sizeW, 0);
T[0] = -1;
int pos = 2, cnd = 0;
while(pos <= sizeW) {
if(W[pos - 1] == W[cnd]) {
T[pos++] = cnd + 1;
cnd ++;
}
else if(cnd > 0)
cnd = T[cnd];
else
T[pos++] = 0;
}
}
void KMP() {
Compute_Prefix();
int m = 0, i = 0;
while(m + i < sizeS) {
if(W[i] == S[m + i]) {
if(i == sizeW - 1)
Sol.push_back(m);
i++;
}
else if(T[i] > -1) {
m = m + i - T[i];
i = T[i];
}
else {
m = m + i + 1;
i = 0;
}
}
}
void Read() {
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
//cin >> W >> S;
scanf("%s%s", W, S);
sizeW = strlen(W);
sizeS = strlen(S);
}
void Write() {
cout << Sol.size() << '\n';
for(int i = 0; i < Sol.size() && i < 1000; ++i)
cout << Sol[i] << ' ';
cout << '\n';
}