Pagini recente » Borderou de evaluare (job #2820776) | Borderou de evaluare (job #1462064) | Cod sursa (job #2170079) | Rezultatele filtrării | Cod sursa (job #2349508)
#include <fstream>
#include <cstring>
#include <vector>
#define NMAX 2000005
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int v[NMAX], n, m, nr;
char A[NMAX], B[NMAX];
vector <int> answer;
void prefix(){
int k = 0;
v[1] = 0;
for(int i=2; i<=n; i++){
while(k && B[k+1] != B[i])
k = v[k];
if(B[k+1] == B[i])
k++;
v[i] = k;
}
}
int main()
{
cin>>(B+1)>>(A+1);
A[0] = ' ';
B[0] = ' ';
n = strlen(B) - 1;
m = strlen(A) - 1;
prefix();
int k = 0;
for(int i=1; i<=m; i++){
while(k && B[k+1] != A[i])
k = v[k];
if(B[k+1] == A[i])
k++;
if(k==n){
nr++;
k = v[k];
answer.push_back(i-n);
}
}
cout<<nr<<'\n';
int size;
if(answer.size() > 1000)
size = 1000;
else
size = answer.size();
for(size_t i = 0; i<size; i++)
cout<<answer[i]<<' ';
return 0;
}