Pagini recente » Cod sursa (job #2906200) | Cod sursa (job #825594) | Cod sursa (job #1600456) | Cod sursa (job #1466258) | Cod sursa (job #856428)
Cod sursa(job #856428)
#include<fstream>
#include<string>
using namespace std;
string a,b;
int i,j,n,m,k,c[2000005],v[1005];
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
getline(f,b);
getline(f,a);
m=b.length();
n=a.length();
for (i=n;i>=1;i--)
a[i]=a[i-1];
for (i=m;i>=1;i--)
b[i]=b[i-1];
for (i=2;i<=m;i++)
{
j=c[i-1];
while ((b[i]!=b[j+1]) && (j>0))
j=c[j];
if (b[i]==b[j+1])
c[i]=j+1;
}
for (i=1;i<=n;i++)
{
while ((a[i]!=b[j+1]) && (j>0))
j=c[j];
if (a[i]==b[j+1])
j++;
if (j==m)
{
if (k<1000)
v[++k]=i-j;
else k++;
}
}
g << k << "\n";
for (i=1;i<=min(k,1000);i++)
g << v[i] << ' ';
return 0;
}