fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //Problem 1 : Number of distinct substrings
  5. int solve_p1(const string &str){
  6.     unordered_set<string>s;
  7.     int cnt =0;
  8.     for(int i =0;i<str.size();i++){
  9.         for(int j=i+1;j<=str.size();j++){
  10.             string sub = str.substr(i, j - i);
  11.             if(s.count(sub)){
  12.                 continue;
  13.             }
  14.             s.insert(sub);
  15.             cnt++;
  16.         }
  17.     }
  18.     return cnt;
  19. }
  20.  
  21. //Problem 2 : common substrings
  22. void solve_p2(string s1,string s2){
  23.  
  24.     unordered_set<string>set1;
  25.     unordered_set<string>set2;
  26.     int cnt =0;
  27.     for(int i =0;i<s1.size();i++){
  28.         for(int j=i+1;j<=s1.size();j++){
  29.             string sub = s1.substr(i, j - i);
  30.             set1.insert(sub);
  31.         }
  32.     }
  33.     for(int i =0;i<s2.size();i++){
  34.         for(int j=i+1;j<=s2.size();j++){
  35.             string sub = s2.substr(i, j - i);
  36.             set2.insert(sub);
  37.         }
  38.     }
  39.     for(auto s : set1){
  40.         if(set2.count(s)){
  41.             cnt++;
  42.             cout << s << " ";
  43.         }
  44.     }
  45.     cout <<"cnt : "<<cnt <<'\n';
  46. }
  47.  
  48. //Problem 3 : cnt unique anagrams
  49. int solve_p3(const string &str){
  50.     set<string>st;
  51.     int cnt = 0;
  52.  
  53.     for(int i = 0; i < str.size(); i++){
  54.         for(int j = i + 1; j <= str.size(); j++){
  55.             string sub = str.substr(i, j - i);
  56.             sort(sub.begin(),sub.end());
  57.             if (!st.count(sub)) {
  58.                 st.insert(sub);
  59.                 cnt++;
  60.             }
  61.         }
  62.     }
  63.     return cnt;
  64. }
  65.  
  66. //Problem 4:
  67. class Node{
  68. public:
  69.     int data;
  70.     Node* next;
  71.     Node(int data){
  72.         this->data =data;
  73.         this->next =nullptr;
  74.     }
  75. };
  76.  
  77. class LinkedList{
  78. private:
  79.     Node* head;
  80.     Node* tail;
  81.     int size;
  82.  
  83. public:
  84.     LinkedList() : head(nullptr), tail(nullptr), size(0) {}
  85.  
  86.     void print() {
  87.         unordered_set<Node*> visited;
  88.         Node* cur = head;
  89.         while (cur) {
  90.             if (visited.find(cur) != visited.end()) {
  91.                 cout << " -> [Cycle detected at " << cur->data << "]\n";
  92.                 return;
  93.             }
  94.             cout << cur->data << " ";
  95.             visited.insert(cur);
  96.             cur = cur->next;
  97.         }
  98.         cout << "\n";
  99.     }
  100.  
  101.     void insert_end(int value) {
  102.         Node* newNode = new Node(value);
  103.         if (!head) {
  104.             head = tail = newNode;
  105.         } 
  106.         else {
  107.             tail->next = newNode;
  108.             tail = newNode;
  109.         }
  110.         size++;
  111.     }
  112.  
  113.     void create_cycle(){
  114.         for(int i =0;i<4;i++){
  115.             insert_end(i);
  116.         }
  117.         Node* now = tail;
  118.         for(int i =0;i<3;i++){
  119.             insert_end(14+i);
  120.         }
  121.         tail->next = now;
  122.     }
  123.  
  124.     void remove_cycle(){
  125.         unordered_set<Node*> visited;
  126.         Node* cur = head;
  127.         while(cur!=nullptr && cur->next !=nullptr){
  128.             if(visited.find(cur->next) !=visited.end()){
  129.                 cur->next =nullptr;
  130.                 cout <<"Cycle found and removed\n";
  131.                 return;
  132.             }
  133.             visited.insert(cur);
  134.             cur = cur->next;
  135.         }
  136.         cout <<"No cycle found\n";
  137.     }
  138. };
  139.  
  140. //Problem 5 :Quadratic Probing
  141. int hash_string(string name , int limit){
  142.     long long sum=0, nn =limit;
  143.     for(int i=0;i<(int)name.size();i++){
  144.         sum = (sum * 26 + name[i] - 'a') % nn;
  145.     }
  146.     return sum % nn;
  147. }
  148.  
  149. class Entry{
  150. public:
  151.     const static int Internal_limit=65407;
  152.     string name;//key
  153.     string phoneNumber;//data
  154.  
  155.     Entry(string name,string phoneNumber):
  156.         name(name),phoneNumber(phoneNumber){ }
  157.  
  158.     int hash(){
  159.         return hash_string(name,Internal_limit);
  160.     }
  161.  
  162.     void print(){
  163.         cout <<setw(2)<< " ("<<name <<", "<<phoneNumber<<") "<<'\n';
  164.     }
  165. };
  166.  
  167. class HashTable{
  168. private:
  169.     int table_size{0};
  170.     vector<Entry*>table;
  171.     Entry* deleted = new Entry(""," ");
  172.  
  173. public:
  174.     HashTable(int table_size):table_size(table_size){
  175.         table.resize(table_size);
  176.     }
  177.  
  178.     bool put(Entry phone){
  179.         int idx = phone.hash() % table_size;
  180.  
  181.         for(int i = 0; i < table_size; i++){
  182.             int probe_idx = (idx + i*i) % table_size;
  183.             if(table[probe_idx]==deleted || !table[probe_idx]){
  184.                 table[probe_idx] = new Entry(phone.name, phone.phoneNumber);
  185.                 return true;
  186.             }
  187.             else if(table[probe_idx]->name == phone.name){
  188.                 table[probe_idx]->phoneNumber = phone.phoneNumber;
  189.                 return true;
  190.             }
  191.         }
  192.         return false;
  193.     }
  194.  
  195.     void rehash(){
  196.         int old_size = table_size;
  197.         table_size *= 2;
  198.         vector<Entry*> old_table = table;
  199.         table.clear();
  200.         table.resize(table_size);
  201.  
  202.         for(auto en : old_table){
  203.             if(en && en != deleted){
  204.                 put(*en);
  205.             }
  206.         }
  207.     }
  208.  
  209.     void print_all(){
  210.         for(int i = 0 ; i < table_size ; i++){
  211.             cout << i <<" ";
  212.             if(table[i]==deleted){
  213.                 cout <<" X ";
  214.             }
  215.             else if(!table[i]){
  216.                 cout<<" E ";
  217.             }
  218.             else{
  219.                 table[i]->print();
  220.             }
  221.             cout <<'\n';
  222.         }
  223.         cout <<"*************************\n";
  224.     }
  225. };
  226.  
  227. int main(){
  228.  
  229.     cout <<"Test problem 1 : \n";
  230.     cout << solve_p1("abcdef") << endl;
  231.  
  232.     cout <<endl<<endl;
  233.     cout <<"Test problem 2 : \n";
  234.     solve_p2("aaab","ab");
  235.  
  236.     cout <<endl<<endl;
  237.     cout <<"Test problem 3 : \n";
  238.     cout << solve_p3("aab")<<endl;
  239.  
  240.     cout <<endl<<endl;
  241.     cout <<"Test problem 4 : \n";
  242.     LinkedList list;
  243.     list.create_cycle();
  244.     list.remove_cycle();
  245.     list.print();
  246.  
  247.     cout <<endl << endl;
  248.     cout <<"Test problem 5 : \n";
  249.     HashTable ht(7);
  250.     ht.put(Entry("alice", "12345"));
  251.     ht.put(Entry("bob", "67890"));
  252.     ht.put(Entry("charlie", "54321"));
  253.     ht.print_all();
  254.     cout <<"Rehashing...\n";
  255.     ht.rehash();
  256.     ht.print_all();
  257.     return 0;
  258. }
  259.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Test problem 1 : 
21


Test problem 2 : 
b ab a cnt : 3


Test problem 3 : 
5


Test problem 4 : 
Cycle found and removed
0 1 2 3 14 15 16 


Test problem 5 : 
0  E 
1  (charlie, 54321) 

2  E 
3  (alice, 12345) 

4  E 
5  (bob, 67890) 

6  E 
*************************
Rehashing...
0  E 
1  E 
2  E 
3  (alice, 12345) 

4  E 
5  (bob, 67890) 

6  E 
7  E 
8  (charlie, 54321) 

9  E 
10  E 
11  E 
12  E 
13  E 
*************************
https://ideone.com/iichBb
language:
C++ (gcc 8.3)
created:
2 days 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!