Pagini recente » Cod sursa (job #1449490) | Cod sursa (job #3192853) | Cod sursa (job #580223) | Cod sursa (job #2491259) | Cod sursa (job #1360821)
#include <fstream>
#include <string>
using namespace std;
#define N 2000005
int n,m,u[N];
string a, b;
void prefix()
{
int i,q=0;
for(i=2;i<=m;i++)
{
while(q&&a[q+1]!=a[i])
q=u[q];
if(a[q+1]==a[i])
q++;
u[i]=q;
}
}
int main()
{
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
int i,q=0,k=0,p[1005];
getline(in,a);
getline(in,b);
a='.'+a;
b=','+b;
m=a.length()-1;
n=b.length()-1;
prefix();
for(i=1;i<=n;i++)
{
while(q&&a[q+1]!=b[i])
q=u[q];
if(a[q+1]==b[i])
q++;
if(q==m)
{
k++;
if(k<=1000)
p[k]=i-m;
q=u[m];
}
}
//out<<n<<' '<<m;
out<<k<<endl;
if(k>1000)
k=1000;
for(i=1;i<=k;i++)
out<<p[i]<<' ';
out<<endl;
return 0;
}