Pagini recente » Cod sursa (job #1023539) | Cod sursa (job #637104) | Cod sursa (job #2928030) | Cod sursa (job #2306870) | Cod sursa (job #1083380)
using namespace std;
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<utility>
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<numeric>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<deque>
const int INFI=(1LL<<29)-100;
const long long INFL=(1LL<<62)-100;
const double eps=1e-10;
const long double pi=acos(-1.0);
const int MAXN=2000010;
char a[MAXN],b[MAXN];
int fail[MAXN];
void build(char a[],int n){
char c;
int i=0;
for(int k=1;k<=n;k++){
c=a[k+1];
i=fail[k];
while(i && c!=fail[i]){
i=fail[i];
}
if(a[i+1]==c){
fail[k+1]=fail[i+1]+1;
}
}
return;
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a+1);
gets(b+1);
a[0]=b[0]=1;
int n=strlen(a)-1;
int m=strlen(b)-1;
build(a,n);
int k=1,i=1,j=1;
vector<int> sl;
while(k<=m){
while(a[i]==b[j] && i<=n){
i++; j++;
}
if(i>n){
sl.push_back(k-1);
}
if(fail[i-1]>0){
k=j-fail[i-1];
}else{
if(j==k){
j++;
}
k=j;
}
if(i>1){
i=fail[i-1]+1;
}
}
printf("%d ",sl.size());
for(unsigned j=0;j<sl.size() && j<1000;j++){
printf("%d ",sl[j]);
}
return 0;
}