Pagini recente » Cod sursa (job #598229) | Cod sursa (job #650674) | Cod sursa (job #2982770) | Cod sursa (job #2565922) | Cod sursa (job #576903)
Cod sursa(job #576903)
using namespace std;
#include<fstream>
char s[2000100],ss[2000100];
int pi[2000100],sol[1010];
int main()
{int m,i,q,nr=0;
ifstream in("strmatch.in");
in.getline(s,2000030);
in.getline(ss,2000030);
in.close();
q=0;
m=strlen(s);
for(i=1;s[i];i++)
{while(q&&s[q]!=s[i])
q=pi[q-1];
if(s[q]==s[i])
q++;
pi[i]=q;
}
q=0;
for(i=0;ss[i];i++)
{while(q&&s[q]!=ss[i])
q=pi[q-1];
if(s[q]==ss[i])
q++;
if(q==m)
{q=pi[m-1];
nr++;
if(nr<=1000)
sol[nr]=i-m+1;
}
}
ofstream out("strmatch.out");
out<<nr<<'\n';
for(i=1;i<=min(nr,1000);i++)
out<<sol[i]<<" ";
out<<'\n';
out.close();
return 0;
}