fork(3) download 
  1. #include <iostream>
  2. #include <ctype.h>
  3. #include <algorithm>
  4. #include <string.h>
  5.  
  6. using namespace std;
  7.  
  8. const unsigned int MAX_STR_LEN = 250000;
  9. const unsigned short NGRAM = 3;
  10. const unsigned int NGRAMS = MAX_STR_LEN-NGRAM;
  11.  
  12. char ngrams[NGRAMS][NGRAM+1] = { 0 };
  13.  
  14. bool notTerminated(const char *ptr) {
  15.     for (int i=0; i<NGRAM; i++) {
  16.         if (ptr[i] == '\0') {
  17.             return false;
  18.         }
  19.     }
  20.     return true;
  21. }
  22.  
  23. bool noSpace(const char *ptr) {
  24.     for (int i=0; i<NGRAM; i++) {
  25.         if (!isalpha(ptr[i])) {
  26.             return false;
  27.         }
  28.     }
  29.     return true;
  30. }
  31.  
  32. int strCmp( const void* a, const void* b)
  33. {
  34.     char const *char_a = *(char const **)a;
  35.     char const *char_b = *(char const **)b;
  36.  
  37.     return strcmp(char_a, char_b);
  38. }
  39. struct FreqNode {
  40.     const char* str;
  41.     unsigned int freq;
  42.     FreqNode *prev;
  43.     FreqNode *next;
  44. };
  45.  
  46. void unlink(FreqNode *node) {
  47.     FreqNode *prev = node->prev;
  48.     FreqNode *next = node->next;
  49.     if (prev && prev->next) {
  50.         prev->next = next;
  51.     }
  52.     if (next && next->prev) {
  53.         next->prev = prev;
  54.     }
  55.     node->next = 0;
  56.     node->prev= 0;
  57. }
  58.  
  59. void insertAfter(FreqNode *insert, FreqNode *after) {
  60.     FreqNode *origNext = after->next;
  61.     after->next = insert;
  62.     insert->prev = after;
  63.     origNext->prev = insert;
  64.     insert->next = origNext;
  65. }
  66.  
  67. void insertFreqNode(FreqNode *orig, const char* ptr) {
  68.     int freq = 0;
  69.     FreqNode *head = orig;
  70.     FreqNode *origHead = head;
  71.     bool needInsert= true;
  72.     while (head->next) {
  73.         freq = origHead->next->freq;
  74.         if (strcmp(head->next->str, ptr) == 0) {
  75.             head->next->freq += 1;
  76.             if (head->next->freq >= freq
  77.                 && origHead->next != head->next) {
  78.                 FreqNode *link = head->next;
  79.                 unlink(link);
  80.                 insertAfter(link, origHead);
  81.             }
  82.             needInsert = false;
  83.             break;
  84.         }
  85.         head = head->next;
  86.     }
  87.     if (needInsert) {
  88.         head->next = new FreqNode();
  89.         head->next->prev = head;
  90.         head->next->next = 0;
  91.         head->next->str = ptr;
  92.         head->next->freq = 1;
  93.     }
  94. }
  95.  
  96. int main()
  97. {
  98.     for (int i=0; i<NGRAMS; i++) {
  99.         ngrams[i][0] =  ngrams[i][1] =  ngrams[i][2] =  ngrams[i][3] = '\0';
  100.     }
  101.  
  102.     const char *str = "thibbbs is a test and aaa it may haaave some abbba reptetitions thibbbs is a test and aaa it may ha";
  103.     cout << "Length: " <<  strlen(str) << endl;
  104.  
  105.     const char *ptr = str;
  106.     int idx = 0;
  107.     while (notTerminated(ptr)) {
  108.         if (noSpace(ptr)) {
  109.             for (int i=0; i<NGRAM; i++) {
  110.                 ngrams[idx][i] = ptr[i];
  111.             }
  112.             ngrams[idx][NGRAM] = '\0';
  113.             idx++;
  114.         }
  115.         ptr++;
  116.     }
  117.  
  118.     FreqNode head = { "HEAD", 0, 0, 0 };
  119.     for (int i=0; i<NGRAMS; i++) {
  120.         if (ngrams[i][0] == '\0') break;
  121.         insertFreqNode(&head, ngrams[i]);
  122.     }
  123.  
  124.  
  125.  
  126.     FreqNode *headPtr = &head;
  127.     int iter = 0;
  128.     while (headPtr->next && iter++<10) {
  129.         cout << headPtr->next->str << " " << headPtr->next->freq << endl;
  130.         headPtr = headPtr->next;
  131.     }
  132.  
  133.     cout << "Winner is: " << head.next->str << " " << " with " << head.next->freq << " occurrences" << endl;
  134.  
  135.     headPtr = head.next;
  136.     while (headPtr) {
  137.         FreqNode *deleteNode = headPtr;
  138.         headPtr = headPtr->next;
  139.         delete deleteNode;
  140.     }
  141.  
  142.    return 0;
  143. }
  144.  
Success #stdin #stdout 0s 4456KB
comments (?)
stdin 
Standard input is empty
stdout 
Length: 99
aaa 3
bbb 3
ibb 2
hib 2
thi 2
bbs 2
tes 2
est 2
and 2
may 2
Winner is: aaa  with 3 occurrences
https://ideone.com/MNFSis
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!