Pagini recente » Cod sursa (job #135831) | Cod sursa (job #1051758) | Cod sursa (job #898663) | Cod sursa (job #481578) | Cod sursa (job #2770043)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
const int Nmax = 2000000;
vector <int> v;
int p[Nmax + 1];
char a[Nmax + 1], b[Nmax + 1];
void prefix_function()
{
int n = strlen((a + 1));
for (int i = 2; i <= n; i++)
{
int j = p[i - 1];
while (j > 0 && a[i] != a[j + 1])
{
j = p[j];
}
if (a[i] == a[j + 1])
{
j++;
}
p[i] = j;
}
}
void match()
{
int m = strlen((b + 1));
int n = strlen((a + 1));
int j = 0;
for (int i = 1; i <= m; i++)
{
while (j > 0 && b[i] != a[j + 1])
{
j = p[j];
}
if (b[i] == a[j + 1])
{
j++;
}
if (j == n)
{
if (v.size() < 1000)
{
v.push_back(i - n);
}
}
}
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> (a + 1) >> (b + 1);
prefix_function();
match();
fout << v.size() << "\n";
for (auto u : v)
{
fout << u << " ";
}
return 0;
}