Pagini recente » Cod sursa (job #715252) | Cod sursa (job #1924642) | Cod sursa (job #486407) | Cod sursa (job #1251947) | Cod sursa (job #1409603)
#include <fstream>
#include <cstring>
using namespace std;
char a[2000002], b[2000002];
int p[2000002];
int pos[1002];
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in >> a;
in >> b;
int n = strlen(a);
int m = strlen(b);
int k = 0;
for (int i = 1; i < n; i++)
{
if (a[i] == a[k])
k++;
else
k = (a[i] == a[0]);
p[i] = k;
}
int j = 0;
int sol = 0;
for (int i = 0; i <= m - n;)
{
for (; j < n; j++)
if (b[i+j] != a[j])
break;
if (j == n)
{
++sol;
if (sol <= 1000)
pos[sol] = i;
}
j--;
if (j < 0)
j = 0;
i += (j+1 - p[j]);
j = p[j];
}
out << sol << '\n';
for (int i = 1; i <= sol && i <= 1000; i++)
out << pos[i] << ' ';
out << '\n';
return 0;
}