jitendra.theta
BAN USER^ and $ can be neglected removed as string without same also mean the same thing. Here is a dyanamic approach to the problem
bool isMatch(const char *s, const char *p) {
int n=strlen(s), m=strlen(p), i, j, chars=0;
//check if pattern have less that equal to character then string
for(i=0; p[i]!='\0'; ++i) if(p[i]!='*' && n<++chars) return false;
vector<bool> dp(n+2,false);
// dp[n] is true fo first time,
// i.e end of string charater is true to enable correct match for last pattern character
// At any time dp[i] == 1 mean we have match from i to n index
for(i=m-1, dp[n]=true; i>=0; --i){
if(p[i]=='*'){
while(i>0 && p[i]==p[i-1]) --i; //skip multiple *
for(j=n; j>=0 && !dp[j]; --j);
for(; j>=0; --j) dp[j]=true;
}else{
for(j=0; j<n+1; ++j)
dp[j]=(p[i]==s[j] || p[i]=='?') ? dp[j+1] : false;
}
}
return dp[0];
}
functionality for operator << can be written as in C++
class Stringlib {
string str;
public:
Stringlib(string s) {
str = s;
}
friend const char* operator<< (Stringlib& data, int num);
};
const char* operator<< (Stringlib& d, int num) {
num = num % d.str.size();
string str = d.str.substr(d.str.size()-num).append(d.str.substr(0,d.str.size()-num));
cout << str << endl;
return str.c_str();
}
int main() {
Stringlib data("Microsoft");
//data << 3;
printf("%s\n", data << 3);
return 0;
}
rest three operators follow in similar fashion
- jitendra.theta April 22, 2014with reference to stackoverflow 500221. here is a DS
class Square
+ name : string
+ accronym : string
class Row
+ left_square : square
+ center_square : square
+ right_square : square
class Face
+ top_row : list of 3 square
+ center_row : list of 3 square
+ bottom_row : list of 3 square
+ rotate(counter_clockwise : boolean) : nothing
class Cube
+ back_face : face
+ left_face : face
+ top_face : face
+ right_face : face
+ front_face : face
+ bottom_face : face
- rotate_face(cube_face : face, counter_clockwise : boolean) : nothing
Here is O(n) solution in C++ (manacher's algorithm)
int* findPalin(char *seq) {
seq = spaceRemovedSequence(seq);
int seqLen = strlen(seq); // length of the given sequence of letters
int lLen = 2 * seqLen + 1; // length of the needed to be formed
int *list = new int(lLen); // creating a array of 2*n+1 times
int ignoreChar=0; // characters to be ignored from the pivot point
for(int i = 0; i < lLen;i++) {
int s = i / 2 - ignoreChar; // start of the palindrome i
int e = i / 2 + i % 2 + ignoreChar; // end of the palindrome i
while (s > 0 and e < seqLen and seq[s - 1] == seq[e])
s -= 1, e += 1; // try matching one left of start and one right of end ans update 's' and 'e'
list[i] = (e - s); // insert in the list about the maximum palindrome from current pivot
int leftEdge = i-list[i]+1; // It is the left edge of the current palindrome foun
ignoreChar = 0; // initially number of character to be ignored in next loop is 0
// it will be updated if any sequence will be found
// between left edge and pivot having its left pivot same as
// left pivot of current palindrome
if(i-1 <= leftEdge) // if current palindrome is 2 or 1 length then dont search
continue;
for (int k = i-1; k > leftEdge; --k) {
if(k - list[k] + 1 <= leftEdge) { // If biggest possible mirror sequence whose left edge is same
// as left edge of the current p[alindrome then
ignoreChar = (k-leftEdge+1)/2; // update charater to be ignored in next loop
break; // goto to the outer for loop
}
list[++i] = list[k]; // else copy the same left part into right part of current pivot
}
}
return list; //return the list in the end
}
find number of set bit. move all at least significant bit for lowest and most significant bit for highest number
void findLowHigh(int num) {
int setbits = __builtin_popcount(num);
int lowest = 0;
int highest = 0;
for(int i=0; i<setbits; ++i) {
lowest += (1<<i);
highest += (1<<(31-i));
}
cout << lowest << endl;
cout << highest << endl;
}
This can be done using subset sum problem
bool dp[sum/2];
memset(dp, sizeof(dp), 0);
dp[0] = 1;
int usingElements[sum/2];
memset(usingElements, sizeof(usingElements),0);
bool findEqualSum(vector<int> arr) {
int len = arr.size();
int sum = 0;
for(int i=0; i<len; ++i) {
sum += arr[i];
}
for(int i=0; i<len; ++i) {
for(int j=sum/2; j>=0; --j) {
if(dp[j]==true && j+arr[i] <= sum/2 && usingElements[j] < len/2) {
dp[j+arr[i]] = true;
usingElements[j+arr[i]] = usingElements[j] + 1;
}
if(dp[sum/2] == true && usingElements[sum/2] == len/2)
return true;
}
}
return false;
}
using Newton Raphson Method, it will converge quadratically
#include<iostream>
using namespace std;
const int EPS=0.0001;
double root(double data) {
double a = data;
double b = 1.0;
while(a - b > EPS) {
cerr << a << " " << b << endl;
a = (a+b) / 2;
b = data / a;
}
return b;
}
int main() {
double i = 10;
double res = root(i);
cout << res << endl;
return 0;
}
Another C++ version
#include <algorithm>
#include <cmath>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
/* Main Code Starts from here */
void bracketPermut(vector<vector<char> >& vii, vector<char>& vi, int l, int r, int n) {
if(l>n)
return;
if(r == n) {
vii.push_back(vi);
return ;
}
else {
if(l>r) {
vi.push_back(')');
bracketPermut(vii, vi, l, r+1, n);
vi.pop_back();
}
vi.push_back('(');
bracketPermut(vii, vi, l+1, r, n);
vi.pop_back();
}
}
vector< vector <char> > bracketPermut(int n) {
vector <vector<char> > vii;
vector<char> vi;
bracketPermut(vii, vi, 0, 0, n);
return vii;
}
int main() {
vector< vector<char> > out = bracketPermut(5);
for(auto i: out) {
for(auto j: i)
cout << j << " ";
cout<< endl;
}
return 0;
}
/*
Given an array, find all unique three-member subsets, with unique being that [0,2,3] and [3,2,0] are the same set. Should run in faster than 2^n time
*/
#include <iostream>
#include <vector>
using namespace std;
/* Main Code Starts from here */
void solve(vector< vector<int> > &vii, vector<int> &res, vector<int> &vi, int pos, int n) {
if(n==3) {
vii.push_back(res);
return;
}
else {
for(int i=pos; i<vi.size(); ++i) {
res.push_back(vi[i]);
solve(vii, res, vi, i+1, n+1 );
res.pop_back();
}
}
}
vector<vector <int> > subset(vector<int> vi) {
vector< vector<int> > vii;
vector<int> subvec;
solve(vii, subvec, vi,0, 0);
return vii;
}
int main() {
int arr[] = {1,2,3,4,5};
vector<int> vi(arr, arr+sizeof(arr)/sizeof(int) );
vector< vector<int> > out = subset(vi);
for(auto i: out) {
for(auto j: i)
cout << j << " ";
cout<< endl;
}
return 0;
}
a simple resursion will solve this
char str[1000];
int n;
void solve(int s , int n) {
if(n==s) {
str[s] = 0;
printf("%s\n", str);
return;
}
FOR(i,0,2) {
if(s<=1) {
str[s] = 'a' + i;
solve(s+1,n);
}
else if('a'+i == str[s-1] || 'a'+i == str[s-2]){
str[s] = 'a' + i;
solve(s+1,n);
}
}
}
int main() {
scanf("%d", &n);
solve(0,n);
return 0;
}
How about having prefix match array for each of the string that need to be matched something similar to KMP.
When a charater is coming from the stream (say getNextChar()) then try to use prefix matching and update the match counte for each one of the string
function for prefix match
And then using the prefix match array of each one for compare with next coming character from string
- jitendra.theta August 04, 2016