Pagini recente » Cod sursa (job #1768176) | Cod sursa (job #2221206) | Cod sursa (job #521016) | Cod sursa (job #1508930)
#include <iostream>
#include <fstream>
#include <cstring>
#define nmax 2000001
using namespace std;
ifstream f("strmatch.in");
ofstream o("strmatch.out");
char a[nmax], b[nmax];
int poz[10001], pref[nmax], lp, ls, nr, k;
void citire()
{
f.getline(a, nmax);
f.getline(b, nmax);
lp = strlen(a);
ls = strlen(b);
}
void pattern()
{
int i, j;
i=1;
j=0;
pref[0] = 0;
while(i < lp)
if(a[i] == a[j])
{
pref[i] = j+1;
i++;
j++;
}
else
if(j == 0)
pref[i++]=0;
else
j=pref[j-1];
}
int cautare()
{
int i, j;
i = 0;
j = 0;
while(i < ls)
if(b[i] == a[j])
{
i++;
j++;
if(j == lp)
{
poz[++k] = i - lp;
j = pref[j-1];
nr++;
}
}
else
if(j == 0)
i++;
else
j = pref[j-1];
return nr;
}
int main()
{
citire();
pattern();
o<<cautare()<<"\n";
if(k > 1000)
k = 1000;
for(int i=1; i<=k; i++)
o<<poz[i]<<" ";
return 0;
}