SCIT3000 Lecture Notes - Lecture 1: Substring

• School: University of Newcastle
• Department: Science and Technology
• Course: SCIT3000
• Professor: M A Z R U I

Document Summary

Sma 462 - analysis and design of algorithms ii. Submit by end of day 9th november, 2016. // method to count number of substring which. // has equal 0, 1 and 2 int getsubstringwithequal012(string str) int n = str. length(); // map to store, how many times a difference. // pair has occurred previously map< pair, int > mp; mp[make_pair(0, 0)] = 1; zc (count of zeroes), oc(count of 1s) and tc(count of twos) In starting all counts are zero int zc = 0, oc = 0, tc = 0; looping into string int res = 0; for (int i = 0; i < n; ++i) // incresing the count of current character if (str[i] == "0") zc++; else if (str[i] == "1") oc++; else tc++; // making pair of differences (z[i] - o[i], // z[i] - t[i]) pair tmp = make_pair(zc - oc, zc - tc); // count of previous occurrences of above pair.