Pagini recente » Cod sursa (job #826059) | Monitorul de evaluare | Cod sursa (job #3318336) | Cod sursa (job #3309933) | Cod sursa (job #1596845)
#include <string>
#include <vector>
#include <fstream>
#include <string.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
int N;
vector <int> poz;
char A[2000005],B[2000005];
int pref[2000005];
void prep(){
int q = 0;
int la = strlen(A+1);
for(int i = 2;i <= la;i++){
while(q > 0 && A[q+1] != A[i]){
q = pref[q];
}
if(A[q+1] == A[i]){
q++;
}
pref[i] = q;
}
}
void kmp(){
prep();
int q = 0;
int la,lb;
la = strlen(A+1);
lb = strlen(B+1);
for(int i = 1;i <= lb;i++){
while(q > 0 && A[q+1] != B[i]){
q = pref[q];
}
if(A[q+1] == B[i]){
q++;
}
if(q == la){
N++;
if(N <= 1000){
poz.pb(i-la);
}
}
}
}
int main(){
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>A+1;
f>>B+1;
kmp();
g<<N<<'\n';
for(auto it : poz){
g<<it<<' ';
}
}