Pagini recente » Cod sursa (job #2678761) | Cod sursa (job #3188824) | Cod sursa (job #1212053) | Cod sursa (job #867017) | Cod sursa (job #1779572)
#include <cstdio>
#include <vector>
using namespace std;
vector<char> a, b;
vector<int> s;
int p[2000005];
void read();
void prefix_table();
void kmp();
void write();
int main()
{
read();
prefix_table();
kmp();
write();
return 0;
}
void read(){
freopen("strmatch.in", "r", stdin);
char q;
do{
scanf("%c", &q);
a.push_back(q);
}while(q != '\n');
do{
scanf("%c", &q);
b.push_back(q);
}while(q != '\n');
a.pop_back();
b.pop_back();
fclose(stdin);
}
void prefix_table(){
int j(0);
for (unsigned i = 1; i < a.size(); ++i){
while (j && a[j] != a[i])
j = p[j];
if (a[j] == a[i])
++j;
p[i] = j;
}
}
void kmp(){
unsigned j(0);
for (unsigned i = 0; i < b.size(); ++i){
while(j && a[j] != b[i])
j = p[j-1];
if (a[j] == b[i])
++j;
if (j == a.size())
s.push_back(i - a.size() + 1);
}
}
void write(){
freopen ("strmatch.out", "w", stdout);
printf ("%d\n", s.size());
for (unsigned i = 0; i < s.size(); ++i)
printf ("%d ", s[i]);
fclose(stdout);
}