Pagini recente » Cod sursa (job #1517095) | Statistici Vornicu Catalina-Cristina (CatalinaPHO) | Cod sursa (job #496006) | Diferente pentru rotatie-lexicografic-minima intre reviziile 36 si 38 | Cod sursa (job #1581350)
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s,s1;
int n,m,k=0,pr[2000001],i,sol[2000001],l;
int main()
{
f>>s>>s1;
n=s.length();
for (i=n;i>=1;i--)
s[i]=s[i-1];
m=s1.length();
for (i=m;i>=1;i--)
s1[i]=s1[i-1];
pr[1]=0;
for (i=2;i<=n;i++)
{
while (k && s[k+1]!=s[i])
k=pr[k];
if (s[k+1]==s[i])
k++;
pr[i]=k;
}
k=0;
for (i=1;i<=m;i++)
{
while(k && s[k+1]!=s1[i])
k=pr[k];
if (s[k+1]==s1[i])
k++;
if (k==n)
{
k=pr[n];
sol[++l]=i-n;
}
}
g<<l<<'\n';
for (i=1;i<=min(l,1000);i++)
g<<sol[i]<<' ';
return 0;
}