Pagini recente » Cod sursa (job #3127166) | Cod sursa (job #2711309) | Cod sursa (job #701124) | Cod sursa (job #998182) | Cod sursa (job #1779575)
#include <cstdio>
#include <vector>
using namespace std;
vector<char> a, b;
vector<int> s;
int p[2000005];
void read();
void prefix_table();
void kmp();
unsigned min(unsigned, unsigned);
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);
}
}
unsigned min(unsigned x, unsigned y){
if (x < y)
return x;
return y;
}
void write(){
freopen ("strmatch.out", "w", stdout);
printf ("%d\n", s.size());
unsigned t = min(s.size(), 1000);
for (unsigned i = 0; i < t; ++i)
printf ("%d ", s[i]);
fclose(stdout);
}