Pagini recente » Cod sursa (job #978375) | Cod sursa (job #781879) | Cod sursa (job #406715) | Cod sursa (job #2061660) | Cod sursa (job #3041601)
///infoarena Potrivirea sirurilor
#include <fstream>
#include <cstring>
#include <vector>
#define NMAX 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m;
char a[NMAX*2], b[NMAX];
int lps[NMAX*2]; int k;
vector<int> ans; LL counter;
int i, j;
int main()
{
fin >>a>>b;
n = strlen(a);
m = strlen(b);
a[n] = '#';
a[n+1] = 0;
strcat(a, b);
k = 0;
for (i = 1; a[i]; ++i)
{
while (k > 0 && a[i] != a[k]) k = lps[k-1];
if (a[i] == a[k]) k++;
lps[i] = k;
}
for (i = 0; b[i]; ++i)
if (lps[i+n+1] == n)
{
counter ++;
if (counter < 1000)
ans.push_back(i-n+1);
}
fout <<counter<<'\n';
for (auto x: ans)
fout <<x<<' ';
fout <<'\n';
fout.close();
return 0;
}