Pagini recente » Cod sursa (job #2038382) | Cod sursa (job #2038431) | Cod sursa (job #2038394) | Cod sursa (job #2038426) | Cod sursa (job #2323297)
#include <fstream>
#include <cstring>
#include <vector>
#define DIM 2000002
using namespace std;
ifstream in ("strmatch.in");
ofstream out("strmatch.out");
char A[DIM], B[DIM];
int lgA, lgB, L;
int prefix[DIM];
vector<int> sol;
int main(int argc, const char * argv[]) {
in>> A + 1 >> B + 1;
lgA = strlen(A + 1);
lgB = strlen(B + 1);
//Precalculare functie prefix pentru A
prefix[1] = 0;
for(int i = 2; i <= lgA; ++ i){
while(L != 0 && A[i] != A[L + 1])
L = prefix[L];
if(A[i] == A[L + 1])
++ L;
prefix[i] = L;
}
//aplicare precalculare pe sirul mare
L = 0;
for(int i = 1; i <= lgB; ++ i){
while(L != 0 && B[i] != A[L + 1])
L = prefix[L];
if(B[i] == A[L + 1])
++ L;
if(L == lgA){
sol.push_back(i - lgA);
L = prefix[L];
}
if(sol.size() == 1000)
break;
}
out<<sol.size()<<'\n';
for(auto it : sol)
out<<it<<" ";
return 0;
}