Pagini recente » Cod sursa (job #626677) | Cod sursa (job #1555272) | Cod sursa (job #2838711) | Cod sursa (job #977737) | Cod sursa (job #2923510)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int nMAX = 2e6;
const int mMAX = 2e6;
int n, m;
char a[nMAX + 2];
char b[mMAX + 2];
int lps[nMAX + 1];
void buildLPS()
{
lps[1] = 0;
int j = 1;
for (int i = 2; i <= n; ++i)
{
if (a[i] == a[j])
lps[i] = j++;
else
{
lps[i] = lps[i-1];
j = 1;
}
}
}
int main()
{
fin >> a+1 >> b+1;
n = strlen(a+1);
m = strlen(b+1);
buildLPS();
vector<int> indici;
int i = 1;
for (int j = 1; j <= m; )
{
if (a[i] == b[j])
{
if (i == n)
{
indici.push_back(j-n);
i = lps[n] + 1;
j++;
}
else
i++, j++;
}
else
{
if (i == 1)
j++;
else
i = lps[i-1] + 1;
}
}
fout << indici.size() << '\n';
for (int x : indici)
fout << x << ' ';
}