Pagini recente » Cod sursa (job #2194640) | Cod sursa (job #2054611) | Cod sursa (job #1694242) | Cod sursa (job #1761293) | Cod sursa (job #711184)
Cod sursa(job #711184)
#include <fstream>
#include <cstring>
using namespace std;
const int N=2000002;
char a[N],text[N];
int p[N],rez[N];
ifstream in("strmatch.in");
ofstream out("strmatch.out");
void prefix()
{
p[0]=-1;
for (int i=2;a[i];i++)
for (int j=p[i-1];j>=0;j=p[j])
if (a[j+1]==a[i])
{
p[i]=j+1;
break;
}
}
int len(char a[],char b[])
{
int i;
for (i=0;a[i] && a[i]==b[i];i++);
return i;
}
void match()
{
int size=strlen(a+1);
for (int i=1,j;text[i];i+=j-p[j])
{
j=len(text+i,a+1);
if (j==size)
rez[++rez[0]]=i-1;
}
}
int main()
{
in>>a+1>>text+1;
prefix();
match();
out<<rez[0]<<"\n";
rez[0]=min(rez[0],1000);
for (int i=1;i<=rez[0];i++)
out<<rez[i]<<" ";
out<<"\n";
return 0;
}