Pagini recente » Cod sursa (job #3309528) | Cod sursa (job #1374082) | Cod sursa (job #3324029) | Cod sursa (job #3245599) | Cod sursa (job #3318844)
#include <fstream>
#include <queue>
#include <string>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main() {
string A, B;
fin >> A >> B;
if(A.size() > B.size()){
fout << 0;
}else{
int sizeA = A.size();
int sizeB = B.size();
int LPS[2000000];
LPS[0] = -1;
for(int indexStr = 1; indexStr < sizeA; indexStr++){
int indexToLookAt = LPS[indexStr - 1];
bool foundOne = false;
while(!foundOne){
if(A.at(indexStr) == A.at(indexToLookAt + 1)){
LPS[indexStr] = indexToLookAt + 1;
foundOne = true;
}else{
if(indexToLookAt == -1)
break;
indexToLookAt = LPS[indexToLookAt];
}
}
if(!foundOne)
LPS[indexStr] = -1;
}
int indexA = 0;
int counterSubsequences = 0;
int positions[1000];
for(int i = 0; i < sizeB; i++){
if(A.at(indexA) == B.at(i)){
indexA++;
if(indexA == sizeA){
counterSubsequences++;
indexA = LPS[indexA - 1] + 1;
if(counterSubsequences < 1000)
positions[counterSubsequences - 1] = i - sizeA + 1;
}
}else{
if(indexA != 0) {
i--;
indexA = LPS[indexA - 1] + 1;
}
}
}
fout << counterSubsequences << "\n";
for(int i = 0; i < min(counterSubsequences, 1001); i++)
fout << positions[i] << " ";
}
return 0;
}