Pagini recente » Cod sursa (job #874949) | Cod sursa (job #256974) | Cod sursa (job #1567025) | Cod sursa (job #2211766) | Cod sursa (job #876857)
Cod sursa(job #876857)
#include <fstream>
#include <string>
using namespace std;
int main ()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a,f;
int t[200000],i,j,n,m,k[1000],h=0;
getline(in,a);
getline(in,f);
a.insert(0,"0");
f.insert(0,"0");
n=a.size();
m=f.size();
j=0;
t[1]=0;
//out<<a<<endl<<f<<endl;
for(i=2;i<=n;i++){
while(j>0&&a[j+1]!=a[i])
j=t[j];
if(a[j+1]==a[i])
j++;
t[i]=j;}
j=0;
// for(i=0;i<n;i++)
// out<<t[i]<<' ';
for(i=0;i<=m;i++){
while(j>0&&a[j+1]!=f[i])
j=t[j];
if(a[j+1]==f[i])
j++;
if(j==n-1){
k[h++]=i-n+1;}}
out<<h<<'\n';
for(i=0;i<h;i++)
out<<k[i]<<' ';
out<<'\n';
return 0;
}