Pagini recente » Cod sursa (job #2571009) | Cod sursa (job #2143555) | Cod sursa (job #1284446) | Cod sursa (job #1704074) | Cod sursa (job #3149558)
#include <bits/stdc++.h>
using namespace std;
#define FAST ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) ;
#define ll long long
ifstream fin("strmatch.in") ;
ofstream fout("strmatch.out") ;
string a,c ;
int z[4000005],n,m,st,dr ;
vector <int> pos ;
int main()
{
fin>>a ;
m=a.size(),c=a+"#";
fin>>a ;
c+=a ;
n=c.size() ;
for(int i=1; i<n; ++i)
{
if(i>dr)
{
st=dr=i ;
while(dr<n && c[dr]==c[dr-st]) dr++ ;
dr--,z[i]=dr-st+1 ;
}
else
{
if(i+z[i-st]<=dr) z[i]=z[i-st] ;
else
{
st=i ;
while(dr<n && c[dr]==c[dr-st]) dr++ ;
z[i]=dr-st ;
}
}
if(z[i]==m && i>m) pos.push_back(i-2*m+2) ;
}
fout<<pos.size()<<'\n' ;
for(int i=0; i<min((int)pos.size(),1000); ++i) fout<<pos[i]<<" ";
return 0;
}