Pagini recente » Cod sursa (job #1564552) | Cod sursa (job #1630770) | Cod sursa (job #2843797) | Cod sursa (job #3306795) | Cod sursa (job #3318829)
#include <fstream>
#include <queue>
#include <string>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
/**
* Longest prefix that is also a suffix
* it is kind of a bit misleading isn't it because you don't do it for the word as a whole
* but instead you do it for the word that is until that letter
* so for a word A, for each of the letter Ai you 'segment' it until the specific character
* and then there you look for the word that ends at the specific character for the prefix that
* is also a suffix
*/
void createLPS(string pattern, int LPS[]){
LPS[0] = -1;
for(int indexStr = 1; indexStr < pattern.size(); indexStr++){
int indexToLookAt = LPS[indexStr - 1] + 1;
if(pattern.at(indexStr) == pattern.at(indexToLookAt))
LPS[indexStr] = indexToLookAt;
else
LPS[indexStr] = -1;
}
}
int main() {
string A, B;
fin >> A >> B;
if(A.size() > B.size()){
fout << 0;
}else{
int LPS[2000000];
createLPS(A, LPS);
int indexA = 0;
int counterSubsequences = 0;
queue<int> positions;
for(int i = 0; i < B.size(); i++){
if(A.at(indexA) == B.at(i)){
indexA++;
if(indexA == A.size()){
counterSubsequences++;
indexA = LPS[indexA - 1] + 1;
if(positions.size() < 1000)
positions.push(i - A.size() + 1);
}
}else{
indexA = LPS[indexA] + 1;
if(indexA != 0)
i--;
}
}
fout << counterSubsequences << endl;
while(!positions.empty()){
fout << positions.front() << " ";
positions.pop();
}
}
return 0;
}