Pagini recente » Cod sursa (job #1446788) | Cod sursa (job #2728401) | Cod sursa (job #1610987) | Cod sursa (job #834701) | Cod sursa (job #2351790)
#include <fstream>
#include <cstring>
#define MAX 2000010
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[MAX], b[MAX];
int lg, lgb, d[MAX], db[MAX];
int c, pozc[MAX];
int main()
{int k, i;
fin >> (a + 1);
fin >> (b + 1);
lg = strlen(a + 1);
lgb = strlen(b + 1);
for(i = 2, k = 0;i<=lg;i++)
{
if(a[i] == a[k + 1])
{
k++;
d[i] = k;
}
else
{
while(a[k + 1] != a[i] && k)
k = d[k];
if(a[k + 1] == a[i])
d[i] = k + 1;
else d[i] = 0;
}
}
for(i=1, k=0;i<=lgb;i++)
{
if(b[i] == a[k + 1])
{
k++;
db[i] = k;
}
else
{
while(a[k + 1] != b[i] && k)
k = d[k];
if(a[k + 1] == b[i])
{db[i] = k + 1; k++;}
else db[i] = 0;
}
if(db[i] == lg){
c++;
pozc[c] = i - lg;
}
}
fout << c << '\n';
for(i=1;i<=c;i++)
fout << pozc[i] << ' ';
return 0;
}