Pagini recente » Cod sursa (job #3288938) | Cod sursa (job #2276054)
#include<iostream>
#include<fstream>
#include<cstring>
#include<queue>
using namespace std;
char a[4000010],b[2000010];
int z[4000010];
queue<int> sol;
int main()
{
int n=0;
int i,k,len1,len;
ifstream t1("strmatch.in");
ofstream t2("strmatch.out");
t1.getline(a,2000010);
t1.getline(b,2000010);
len1=strlen(a);
strcat(a,"@");
strcat(a,b);
len=strlen(a);
//cout<<a<<' '<<b<<' '<<len1<<' '<<len<<'\n';
int L=0,R=0;
for(i=1;i<len;i++)
{
if( i>R)
{
L=R=i;
while( R<len && a[R-L]==a[R])
R++;
z[i]=R-L;
R--;
}
else
{
k=i-L;
if( z[k]< R-i+1 )
z[i]=z[k];
else
{
L=i;
while( R<len && a[R-L]==a[R])
R++;
z[i]=R-L;
R--;
}
}
if(z[i]==len1)
{
n++;
if(n<=1000) sol.push(i-len1-1);
}
}
t2<<n<<'\n';
for(i=0;i<min(1000,n);i++,sol.pop())
t2<<sol.front()<<' ';
t2<<'\n';
return 0;
}