Pagini recente » Cod sursa (job #2801711) | Cod sursa (job #1917952) | Cod sursa (job #2307219) | Cod sursa (job #18836) | Cod sursa (job #2472365)
#include <bits/stdc++.h>
#define NMAX 2000001
using namespace std;
char a[NMAX], b[NMAX];
size_t last[NMAX], sol[1001], gasite = 0;
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin.getline(a, NMAX, '\n');
size_t la = strlen(a);
fin.getline(b, NMAX, '\n');
size_t lb = strlen(b);
for(size_t k = 0, i = 1; i < la; ++i)
{
while(k > 0 && a[i] != a[k]) k = last[k - 1];
if(a[i] == a[k]) ++k;
last[i] = k;
}
for(size_t k = 0, i = 0; i < lb; ++i)
{
while(k > 0 && a[k] != b[i]) k = last[k - 1];
if(a[k] == b[i]) ++k;
if(k == la)
{
if(++gasite <= 1000) sol[gasite] = i - la + 1;
}
}
fout << gasite << '\n';
if(gasite > 1000) gasite = 1000;
for(size_t i = 1; i <= gasite; ++i) fout << sol[i] << ' ';
}