Pagini recente » Cod sursa (job #2042893) | Cod sursa (job #1764743) | Cod sursa (job #1365879) | Cod sursa (job #476492) | Cod sursa (job #1135528)
#include<fstream>
#include<string>
using namespace std;
const int maxn = 2000005;
string s, t;
int a[maxn],x[1005];
void make_prefix(){
int k=0,n=0,m=t.size();
for(int i=1;i<m;i++){
while(k && t[k]!=t[i])k=a[k];
if(t[k]==t[i])k++;
a[i]=k;
}
}
main(){
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin>>t>>s;
int k=0,n=0,m=t.size();
a[0]=0;
make_prefix();
k=0;
for(int i=0;i<s.size();i++){
while(k && t[k]!=s[i])k=a[k-1];
if(t[k]==s[i])k++;
if(k==m){
k=a[m-1];
n++;
if(n<1002)
x[n]=i-m+1;
}
}
fout<<n<<"\n";
if(n>1000)n=1000;
for(int i=1;i<=n;i++)fout<<x[i]<<" ";
}