Pagini recente » Cod sursa (job #895720) | Cod sursa (job #1465150) | Cod sursa (job #1595554) | Cod sursa (job #89039) | Cod sursa (job #2471512)
#include <bits/stdc++.h>
using namespace std;
size_t lcsp[2000001]; //cel mai lung sufix care e si prefix
size_t sol[1001];
char a[2000001];
char b[2000001];
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin.getline(a, 2000000, '\n');
fin.getline(b, 2000000, '\n');
for(size_t k = 0, i = 1; a[i] != '\0'; ++i)
{
while(k && a[k] != a[i]) k = lcsp[k - 1];
if(a[i] == a[k]) ++k;
lcsp[i] = k;
}
size_t gasite = 0, n = strlen(a);
for(size_t k = 0, i = 1; b[i] != '\0'; ++i)
{
while(k && a[k] != b[i]) k = lcsp[k - 1];
if(a[k] == b[i]) ++k;
if(k == n)
{
sol[++gasite] = i - k + 1;
if(gasite == 1000) break;
}
}
fout << gasite << '\n';
for(size_t i = 1; i <= gasite; ++i) fout << sol[i] << ' ';
}