Pagini recente » Cod sursa (job #1629633) | Cod sursa (job #884421) | Cod sursa (job #491466) | Cod sursa (job #2461069) | Cod sursa (job #3256306)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,M,N,i,j,q;
char s[2000003],t[2000003];
int pi[2000003],pos[1003];
int main()
{
f>>s;
M=strlen(s);
for (i=M;i>0;i--){
s[i]=s[i-1];
}
f>>t;
N=strlen(t);
for (i=N;i>0;i--){
t[i]=t[i-1];
}
//cout<<M<<' '<<N<<' '<<(s+1)<<' '<<(t+1);
for (i=2;i<=M;i++){
while(q&&s[i]!=s[q+1])
q=pi[q];
if (s[i]==s[q+1])q++;
pi[i]=q;
}
for (i=1;i<=N;i++){
while (q&&s[q+1]!=t[i])
q=pi[q];
if (s[q+1]==t[i])
q++;
if (q==M){
n++;
q=pi[M];
if (n<=1000){
pos[n]=i-M;
}
}
}
g<<n<<'\n';
for (i=1;i<=n;i++){
g<<pos[i]<<' ';
}
return 0;
}