Pagini recente » Cod sursa (job #2313258) | Cod sursa (job #2371829) | Cod sursa (job #1306560) | Cod sursa (job #1163085) | Cod sursa (job #1163625)
#include <fstream>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
#define MAX 2000001
char A[MAX], B[MAX];
int prefix[MAX], s[MAX];
int al,sn;
void make_prefix(){
int k=0;
al=1;
for (int i=2;A[i];i++) {
al++;
while (k>0 && A[k+1]!=A[i])
k=prefix[k];
if (A[k+1]==A[i])
k++;
prefix[i]=k;
}
}
int main(){
in.getline(A + 1, MAX);
in.getline(B + 1, MAX);
make_prefix();
int k=0;
for (int i=1;B[i];i++) {
while (k>0 && A[k+1]!=B[i])
k=prefix[k];
if (A[k+1]==B[i])
k++;
if (k==al)
s[++sn]=i-al;
}
out<<sn<<"\n";
if (sn>1000) sn=1000;
for (int i=1;i<=sn;i++)
out<<s[i]<<" ";
out<<"\n";
return 0;
}