Pagini recente » Cod sursa (job #2000397) | Cod sursa (job #1567804) | Cod sursa (job #2830235) | Istoria paginii home | Cod sursa (job #1088925)
#include <fstream>
using namespace std;
int n, k, pr[2000001], i, m, rez[1001], nr;
char a[2000001], b[2000001];
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.getline(a+1, 1000);
f.getline(b+1, 1000);
n=strlen(a+1);
m=strlen(b+1);
k=0;
pr[1]=0;
for(i=2; i<=n; i++)
{
while(k>0 && a[k+1]!=a[i])
k=pr[k];
if(a[k+1]==a[i])
k++;
pr[i]=k;
}
k=0;
for(i=1; i<=m; i++)
{
while(k>0 && a[k+1]!=b[i])
k=pr[k];
if(a[k+1]==b[i])
k++;
if(k==n)
{
k=pr[n];
nr++;
if(nr<=1000)
rez[nr]=i-n+1;
}
}
g<<nr<<"\n";
for(i=1; i<=min(1000, nr); i++)
{
g<<rez[i]-1<<" ";
}
}