ZhenjaMax

lab5_2

Jun 10th, 2021
623
9 hours
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define LOGGING false
  2. #define WILD_MODE true
  3.  
  4. #define ROOT_SYMBOL '#'
  5. #define WILD_OFF '\0'
  6.  
  7. #include <iostream>
  8. #include <vector>
  9. #include <string>
  10. #include <algorithm>
  11.  
  12. using namespace std;
  13.  
  14. bool compPairAscending(const pair<int,int> &a, const pair<int,int> &b){
  15.     return (a.first < b.first)||((a.first == b.first)&&(a.second < b.second));
  16. }
  17.  
  18. class TrieElement{
  19. private:
  20.     char symbol;
  21.     int sampleIndex = 0, trieDepth;                 // sampleIndex != 0 - здесь заканчивается строка; trieDepth - длина строки
  22.     vector<TrieElement*> adjacentTrieElements;      // Соседние элементы снизу
  23.     TrieElement* suffixPointer = nullptr;           // Суффиксный указатель
  24.     TrieElement* parentPointer;                     // Указатель на родителя
  25.     vector<int> wildSubstringVector;
  26.  
  27. public:
  28.     TrieElement(char symbol, int trieDepth, TrieElement* parent = nullptr): symbol(symbol), trieDepth(trieDepth), parentPointer(parent){
  29.         if(parentPointer == nullptr)
  30.             parentPointer = this;
  31.     };
  32.     ~TrieElement(){
  33.         for(int i = 0; i < adjacentTrieElements.size(); i++)
  34.             delete adjacentTrieElements[i];
  35.     };
  36.  
  37.     char getSymbol(){ return symbol; };
  38.     int getTrieDepth(){ return trieDepth; };
  39.     void setSampleIndex(int index){ sampleIndex = index; };
  40.     int getSampleIndex(){ return sampleIndex; };
  41.     vector<TrieElement*> getAdjacentTrieElements(){ return adjacentTrieElements; };
  42.     TrieElement* getParentPointer(){ return parentPointer; };
  43.  
  44.     TrieElement* getNextElement(char findSymbol){
  45.         for(int i = 0; i < adjacentTrieElements.size(); i++)
  46.             if(adjacentTrieElements[i]->getSymbol() == findSymbol)
  47.                 return adjacentTrieElements[i];
  48.         return nullptr;
  49.     };
  50.  
  51.     TrieElement* addNextElement(char nextSymbol){
  52.         TrieElement* nextElementPointer = getNextElement(nextSymbol);
  53.         if(nextElementPointer != nullptr)
  54.             return nextElementPointer;
  55.         nextElementPointer = new TrieElement(nextSymbol, this->getTrieDepth()+1, this);
  56.         adjacentTrieElements.push_back(nextElementPointer);
  57.         return nextElementPointer;
  58.     };
  59.  
  60.     TrieElement* findSuffixPointer(char findSymbol){
  61.         for(int i = 0; i < adjacentTrieElements.size(); i++)
  62.             if(adjacentTrieElements[i]->getSymbol() == findSymbol)
  63.                 return adjacentTrieElements[i];
  64.         if(this->getSymbol() == ROOT_SYMBOL)
  65.             return this;
  66.         else
  67.             return suffixPointer->findSuffixPointer(findSymbol);
  68.     };
  69.     TrieElement* getSuffixPointer(){ return suffixPointer; };
  70.     void setSuffixPointer(TrieElement* suffix){ suffixPointer = suffix; };
  71.  
  72.     void pushWildSubstringIndex(int wildIndex){ wildSubstringVector.push_back(wildIndex); };
  73.     vector<int> getWildSubstringVector(){ return wildSubstringVector; };
  74. };
  75.  
  76. class Trie{
  77. private:
  78.     TrieElement* root;
  79.     string textString;
  80.     vector<pair<int, int>> answer;
  81.  
  82.     bool isWildSearch;
  83.     char wildSymbol = WILD_OFF;
  84.     vector<int> answerWild;
  85.     int wildSubstringCount = 0, wildSubstringLength = 0;
  86.  
  87. public:
  88.     Trie(){
  89.        root = new TrieElement(ROOT_SYMBOL, 0);
  90.     };
  91.     ~Trie(){
  92.         delete root;
  93.     };
  94.  
  95.     void getInput(bool isWildInput = false){
  96.         int stringNumber;
  97.         string tempString;
  98.         TrieElement* tempElementPointer;
  99.  
  100.         isWildSearch = isWildInput;
  101.         getline(cin, textString);
  102.         if(!isWildInput){
  103.             cin >> stringNumber;
  104.             cin.ignore(1);
  105.             for(int i = 0; i < stringNumber; i++){
  106.                 getline(cin, tempString);
  107.                 tempElementPointer = root;
  108.                 for(int j = 0; j < tempString.size(); j++)
  109.                     tempElementPointer = tempElementPointer->addNextElement(tempString[j]);
  110.                 tempElementPointer->setSampleIndex(i+1);
  111.             }
  112.         } else {
  113.             getline(cin, tempString);
  114.             cin >> wildSymbol;
  115.  
  116.             wildSubstringLength = tempString.size();
  117.             int wildSubstringIndex;
  118.             tempElementPointer = root;
  119.  
  120.             tempString += wildSymbol;
  121.             for(int i = 0; i < tempString.size(); i++){
  122.                 if(tempString[i] == wildSymbol){
  123.                     if(tempElementPointer != root){
  124.                         wildSubstringIndex = i-tempElementPointer->getTrieDepth();
  125.                         tempElementPointer->setSampleIndex(1);
  126.                         tempElementPointer->pushWildSubstringIndex(wildSubstringIndex);
  127.                         wildSubstringCount++;
  128.                         tempElementPointer = root;
  129.                     }
  130.                 } else
  131.                     tempElementPointer = tempElementPointer->addNextElement(tempString[i]);
  132.             }
  133.         }
  134.         return;
  135.     };
  136.  
  137.     void linkTrieSuffix(){
  138.         vector<TrieElement*> queue, ajacentTempVector, ajacentRootVector;
  139.         TrieElement *tempSuffixElem, *tempCurrentElem;
  140.         char queueSymbol;
  141.  
  142.         root->setSuffixPointer(root);
  143.         ajacentRootVector = root->getAdjacentTrieElements();
  144.         for(int i = 0; i < ajacentRootVector.size(); i++){
  145.             ajacentRootVector[i]->setSuffixPointer(root);
  146.             ajacentTempVector = ajacentRootVector[i]->getAdjacentTrieElements();
  147.             queue.insert(queue.end(), ajacentTempVector.begin(), ajacentTempVector.end());
  148.         }
  149.  
  150.         while(queue.size() != 0){
  151.             queueSymbol = queue[0]->getSymbol();
  152.             tempCurrentElem = queue[0]->getParentPointer();
  153.             tempSuffixElem = nullptr;
  154.  
  155.             while(tempSuffixElem == nullptr){
  156.                 tempCurrentElem = tempCurrentElem->getSuffixPointer();
  157.                 tempSuffixElem = tempCurrentElem->getNextElement(queueSymbol);
  158.                 if((tempCurrentElem == root) && (tempSuffixElem == nullptr))
  159.                     tempSuffixElem = root;
  160.             }
  161.             queue[0]->setSuffixPointer(tempSuffixElem);
  162.  
  163.             ajacentTempVector = queue[0]->getAdjacentTrieElements();
  164.             if(ajacentTempVector.size() != 0)
  165.                 queue.insert(queue.end(), ajacentTempVector.begin(), ajacentTempVector.end());
  166.             queue.erase(queue.begin());
  167.         }
  168.     };
  169.    
  170.  
  171.     void search(){
  172.         TrieElement* currentElem = root, *suffixTraceback;
  173.         int tracebackSampleIndex, wildSuffixCountIndex;
  174.         vector<int> wildSuffixCountVector(textString.size(), 0);
  175.         vector<int> wildTempSubstringVector;
  176.  
  177.         for(int i = 0; i < textString.size(); i++){
  178.             currentElem = currentElem->findSuffixPointer(textString[i]);
  179.             suffixTraceback = currentElem;
  180.             while(suffixTraceback != root){
  181.                 tracebackSampleIndex = suffixTraceback->getSampleIndex();
  182.                 if(tracebackSampleIndex != 0){
  183.                     if(!isWildSearch)
  184.                         answer.push_back(pair<int, int>(i+2 - suffixTraceback->getTrieDepth(), tracebackSampleIndex));
  185.                     else{
  186.                         wildTempSubstringVector = suffixTraceback->getWildSubstringVector();
  187.                         for(int j = 0; j < wildTempSubstringVector.size(); j++){
  188.                             wildSuffixCountIndex = i-wildTempSubstringVector[j]-suffixTraceback->getTrieDepth()+1;
  189.                             if(wildSuffixCountIndex >= 0)
  190.                                 wildSuffixCountVector[wildSuffixCountIndex]++;
  191.                         }
  192.                     }
  193.                 }
  194.                 suffixTraceback = suffixTraceback->getSuffixPointer();
  195.             }
  196.         }
  197.         if(!isWildSearch)
  198.             sort(answer.begin(), answer.end(), compPairAscending);
  199.         else
  200.             for(int i = 0; i <= textString.size() - wildSubstringLength; i++)
  201.                 if(wildSuffixCountVector[i] == wildSubstringCount)
  202.                     answerWild.push_back(i+1);
  203.         return;
  204.     };
  205.  
  206.     void printAnswer(){
  207.         if(!isWildSearch)
  208.             for(int i = 0; i < answer.size(); i++)
  209.                 cout << answer[i].first << " " << answer[i].second << endl;
  210.         else
  211.             for(int i = 0; i < answerWild.size(); i++)
  212.                 cout << answerWild[i] << endl;
  213.         return;
  214.     };
  215.  
  216.     void printTrieRecursive(TrieElement* currentElem){
  217.         cout << currentElem->getSymbol() << "\t" << currentElem->getSampleIndex() << "\t" << currentElem->getTrieDepth() << "\t|\t"
  218.             << currentElem << "\t" << currentElem->getParentPointer() << "\t" << currentElem->getSuffixPointer() << endl;
  219.         vector<TrieElement*> adjacentCurrent = currentElem->getAdjacentTrieElements();
  220.         if(adjacentCurrent.size() != 0)
  221.             for(int i = 0; i < adjacentCurrent.size(); i++)
  222.                 printTrieRecursive(adjacentCurrent[i]);
  223.         return;
  224.     };
  225.  
  226.     void printTrie(){
  227.         cout << "char\tsample\tdepth\t|\tpointer\t\tparent\t\tsuffix\n";
  228.         printTrieRecursive(root);
  229.         return;
  230.     };
  231.  
  232. };
  233.  
  234. int main(){
  235.     Trie trie;
  236.     trie.getInput(WILD_MODE);
  237.     trie.linkTrieSuffix();
  238.     if(LOGGING)
  239.         trie.printTrie();
  240.     trie.search();
  241.     trie.printAnswer();
  242.     return 0;
  243. }
  244.  
RAW Paste Data