sscanf

to read in the numbers in the following string

string s = "1000 ml of water, weighing 1000 g"

int v;
sscanf(s, "%d ml of", &v);

size_t p = s.find(',');

int m;
sscanf(s.substr(p+2, s.length()-p).c_str(), "weighing %d", &m);

Note: the use of c_str() and sscanf()

STL comparison FUNCTOR

http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm374

#include < iostream >
#include < vector >
#include < string >
#include < algorithm >
using namespace std;

bool isvowl(char c) {
  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
    return true;
  return false;
  
}

struct word {
  string w;
  vector s1; //sorted
  vector s2; //unsorted
};

// comparison function
bool operator < (const word &a, const word &b) {
  if (a.s1 != b.s1) return a.s1 < b.s1;
  return a.s2 < b.s2;
}  

  
class SyllableSorting {
public:
  
  vector  sortWords(vector  words) {
    
    vector vw;

    
    for(int i = 0; i < words.size(); ++i) {
    
      vector syl;
      word W;
          
      string s("");
      s += words[i][0];
          
      for (int j = 1; j < words[i].length(); ++j) {
        char c = words[i][j];
        bool pv = isvowl(words[i][j-1]);
        bool v  = isvowl(c);
        if (pv) { //previous char is a vowl
          if (v)
            s += c;
          else {
            syl.push_back(s);
            s = c;
          }
        } else {  // previous char is a consonant
          s += c;
        } 
      }
      syl.push_back(s);
      
      for(int k = 0; k < syl.size(); ++k)
        cout << syl[k] << "  ";
      cout << endl;
      
      W.w = words[i];
      
      W.s2 = (syl);
      
      sort(syl.begin(), syl.end());
      
      W.s1 = (syl);
           
      vw.push_back(W);
    
    }
    
    sort(vw.begin(), vw.end());
    vector ret;
    for(int i = 0; i < vw.size(); ++i)
      ret.push_back(vw[i].w);
    return ret;
  }
};

String Searching

http://allisons.org/ll/AlgDS/Strings/

http://en.wikipedia.org/wiki/String_searching_algorithm

http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm

Suffix Tree

Tries and suffix tree

wiki - Suffix Trees

http://allisons.org/ll/AlgDS/Tree/Suffix/

 

The suffix tree can be built in O(n) time (linear time regarding the length of strings) due to Ukkonen (1995).

Applications: [1,2,3] from http://allisons.org/ll/AlgDS/Tree/Suffix/

1. String Search: Searching for a substring, pat[1..m], in txt[1..n], can be solved in O(m) time (after the suffix tree for txt has been built in O(n) time).
2. Palindromes: The longest palindrome of txt[1..n] can be found in O(n) time, e.g. by building the suffix tree for txt$reverse(txt)# or by building the generalized suffix tree for txt and reverse(txt).
3. Longest Common String:  The longest common substring of two strings, txt1 and txt2, can be found by building a generalized suffix tree for txt1 and txt2: Each node is marked to indicate if it represents a suffix of txt1 or txt2 or both. The deepest node marked for both txt1 and txt2 represents the longest common substring.  Equivalently, one can build a (basic) suffix tree for the string txt1$txt2#, where `$' is a special terminator for txt1 and `#' is a special terminator for txt2. The longest common substring is indicated by the deepest fork node that has both `...$...' and `...#...' (no $) beneath it.