Pagini recente » Cod sursa (job #985072) | Cod sursa (job #1830316) | Cod sursa (job #2295141) | Cod sursa (job #581066) | Cod sursa (job #1360768)
#include <fstream>
#include <string>
using namespace std;
#define N 2000003
int n,m,u[N],p[N];
string a, b;
void prefix()
{
int i,q=0;
for(i=2;i<=n;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;
getline(in,b);
getline(in,a);
a='.'+a;
b=','+b;
n=a.length()-1;
m=b.length()-1;
prefix();
for(i=1;i<=m;i++)
{
while(q&&a[q+1]!=b[i])
q=u[q];
if(a[q+1]==b[i])
q++;
if(q==n)
{
out<<i-n+1<<' ';
q=u[n];
k++;
}
}
out<<endl<<k<<endl;
return 0;
}