Pagini recente » Cod sursa (job #2414589) | Cod sursa (job #2489171) | Cod sursa (job #1337063) | Cod sursa (job #1177020) | Cod sursa (job #2198939)
#include <iostream>
#include <fstream>
#include <cstring>
#define NUM 2000005
char a[NUM];
char b[NUM];
int pi[NUM], poz[1024];
int n, la, lb;
using namespace std;
void prefix()
{
int k = 0;
pi[1] = 0;
for(int i = 2; i < la; ++i)
{
while(a[k + 1] != a[i] && k > 0)
k = pi[k];
if(a[k + 1] == a[i])
k++;
pi[i] = k;
}
}
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f >> a >> b;
la = strlen(a);
lb = strlen(b);
for(int i = la; i >= 1; --i)
a[i] = a[i-1];
for(int i = lb; i >= 1; --i)
b[i] = b[i-1];
la++, lb++;
prefix();
int k = 0;
for(int i = 1; i < lb; ++i)
{
while(a[k + 1] != b[i] && k > 0)
k = pi[k];
if(a[k + 1] == b[i])
k++;
if(k == la - 1)
{
n++;
if(n <= 1000)
poz[n] = i - k;
k = pi[k];
}
}
g << n << "\n";
if(n > 1000)
n = 1000;
for(int i = 1; i <= n; ++i)
g << poz[i] << " ";
f.close();
g.close();
}