Pagini recente » Cod sursa (job #801341) | Cod sursa (job #2289978) | Cod sursa (job #2174061) | Cod sursa (job #2566388) | Cod sursa (job #1779593)
#include <cstdio>
#include <vector>
using namespace std;
vector<char> a, b;
vector<int> s;
bool same = 1;
int p[2000005];
void read();
void prefix_table();
void kmp();
unsigned min(unsigned, unsigned);
void write();
int main()
{
read();
if (same){
freopen ("strmatch.out", "w", stdout);
printf ("1\n0\n");
fclose(stdout);
return 0;
}
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');
int t = -1;
do{
scanf("%c", &q);
if (t+1 < a.size() && q != '\n' && q != a[++t])
same = 0;
b.push_back(q);
}while(q != '\n');
if (a.size() != b.size())
same = 0;
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-1];
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);
}