Pagini recente » Atasamentele paginii Bsrec | Cod sursa (job #3354264) | Cod sursa (job #3325216) | Cod sursa (job #2038399) | Cod sursa (job #2323298)
#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];
}
}
out<<sol.size()<<'\n';
int size = min((int)sol.size(), 1000);
for(int i = 0; i < size; ++ i)
out<<sol[i]<<" ";
return 0;
}