Pagini recente » Cod sursa (job #124984) | Cod sursa (job #1168306) | Cod sursa (job #1633845) | Cod sursa (job #2770414) | Cod sursa (job #463917)
Cod sursa(job #463917)
#include<cstring>
#include<fstream>
#include<vector>
using namespace std;
char a[2000001], b[2000001];
int prefix[2000001];
vector<int> pos;
void make_prefix()
{
int k = -1;
prefix[0] = -1;
for (int i = 1; i < strlen(a); ++i)
{
while (k != -1 && a[k + 1] != a[i])
k = prefix[k];
if (a[k + 1] == a[i])
++k;
prefix[i] = k;
}
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> a >> b;
make_prefix();
int ok = -1;
for (int i = 0; i < strlen(b); ++i)
{
if (a[ok + 1] == b[i])
++ok;
else
while (ok != -1 && a[ok + 1] != b[i])
ok = prefix[ok];
if (ok == strlen(a) - 1)
{
pos.push_back(i - strlen(a) + 1);
ok = prefix[ok];
}
}
fout << pos.size() << '\n';
for (int i = 0; i < pos.size(); ++i)
fout << pos[i] << ' ';
}