Pagini recente » Cod sursa (job #2507082) | Cod sursa (job #1522481) | Cod sursa (job #2033886) | Cod sursa (job #1527550) | Cod sursa (job #2305108)
#include <fstream>
#include <string>
#define lim 2000004
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int pre[lim],na,nb,ap[lim];
string a,b;
void prefix (void)
{
int j=0;
for (int i=2;i<=na;i++)
{
while (j && a[j+1]!=a[i]) j=pre[j];
if (a[j+1]==a[i]) j++;
pre[i]=j;
}
}
int main()
{
f>>a>>b;
na=a.length();
nb=b.length();
for (int i=na-1;i>=0;i--) a[i+1]=a[i];
for (int i=nb-1;i>=0;i--) b[i+1]=b[i];
prefix();
int j=0;
for (int i=1;i<=nb;i++)
{
while (j && a[j+1]!=b[i]) j=pre[j];
if (a[j+1]==b[i]) j++;
if (j==na)
{
j=pre[j];
ap[0]++;
ap[ap[0]]=i-na+1;
}
}
g<<ap[0]<<'\n';
ap[0]=minim(ap[0],1000);
for (int i=1;i<=ap[0];i++) g<<ap[i]-1<<' ';
f.close();
g.close();
return 0;
}