CareerCup

I really do not understand why ppl bluntly paste codes here. Please either well comment your code or write algorithm as well. We are not machines which can compile your un-formatted code and deduce the algorithm.

I think a modified Boyer-Moore's algorithm will serve the purpose.

hey i found this solution on website "Mycareerstack.com" and i think it is right.


#include < iostream >
#include < string.h >
using namespace std;

int main()
{
char input1[100]; //First input string
char input2[100]; // Second input string

cout < < "enter the First String" < < endl;
scanf("%s", input1);
cout < < "enter the Second String" < < endl;
scanf("%s", input2);
int len1=strlen(input1); //computing length of first Input
int len2=strlen(input2); //computing length of Second Input
int flag=0;
int times=0; //Flag to indicate how many places to shift to left
int j=0; //for traversing second string
for(int i=0;input1[i]!='\0';i++)//To remove all occurences in one go Without using extra space
{
input1[i-flag]=input1[i];
int k=0;
if(input1[i]==input2[j])
{

j++;
if(j==len2) //if whole of the second input is found then move up coming alphabets
//to left by value in flag.
{
flag=j;
times++;
j=0;
}
}
else
{ j=0;
continue;
}
}
cout < < times*flag < < endl;
len1=len1-times*flag;
input1[len1]='\0';
cout < < input1;

system("pause");
return 0;
}

void remove_occurrences_of(const std::string& s2, std::string& s1)
{
typedef std::pair<bool, size_t> item;
std::vector<item> s(255, item(false, 0));
for(size_t i = 0; i < s2.size(); ++i) {
s[s2[i]] = item(true, i);
}
size_t k = 0;
for(size_t j = 0; j < s1.size(); ++j) {
if(k == s2.size()) {
assert(j >= k);
s1.erase(j - k, k);
}
if(s[s1[j]].first && s[s1[j]].second == k) {
++k;
} else {
k = 0;
}
}
}

Sorry some corrections to the above algorithm:

void remove_occurences(std::string& s1, const std::string& s2)
{
    typedef std::pair<bool, size_t> item;
    std::vector<item> s(255, item(false, 0));
    for(size_t i = 0; i < s2.size(); ++i) {
        s[s2[i]] = item(true, i);
    }
    size_t k = 0;
    size_t j = 0;
    while(j < s1.size()) {
        if(s[s1[j]].first && s[s1[j]].second == k) {
            ++k;
        } else {
            k = 0;
        }
        if(k == s2.size()) {
            assert(j + 1 >= k);
            size_t l = j + 1 - k;
            s1.erase(l, k);
            j = l;
            k = 0;
        } else {
            ++j;
        }
    }
}

public class StringPatternOccuranceRemove {
public static void main(String[] args){
String str = "skjthshetheshetesm";
String patt = "she";
String newString = "";
String tmpString = "";
int count = 0;
for ( int i = 0; i < str.length(); ++i){
char ch = str.charAt(i);
if ( ch == patt.charAt(count)){
count++;
tmpString+=ch;
if ( count == patt.length() ){
tmpString="";
count = 0;
}
}else{
if ( count > 0 ){
newString+=tmpString+ch;
tmpString="";
count=0;
}else{
count = 0;
newString=newString+str.charAt(i);
}
}
}
System.out.println("New String : "+newString);
}
}

O(N) soln.

void RemoveOccurance(char *s1, char *s2) {
    int m = strlen(s1);
    int n = strlen(s2);
    char result[m+1], match[n+1];
    int j = 0, k = 0;
    memset(result,0,sizeof(result));
    memset(match, 0, sizeof(match));
    for(int i=0;i<m;i++) {
        if(s1[i]==s2[j]) {
            match[j] = s2[j];
            j++;
            if(j==n) {
                memset(match,0,sizeof(match));
            }
        }
        else {
            for(int l=0;l<strlen(match);l++) result[k++] = match[l];
            result[k++] = s1[i];
            j=0;
            memset(match,0,sizeof(match));
            if(s1[i]==s2[j]) {
                match[j] = s2[j];
                j++;
            }
        }
    }
    result[k] = '\0';
    printf("%s\n",result);
}

Can't we use java method?
Maybe this method need to be called unless string wasn't changed?

public String removeOdds(String a, String b) {
		//using substr?
		if (b.length() == 0 ) return a;
		StringBuffer s = new StringBuffer();
		int i = 0;
		while(i<a.length()) {
			int nextB = a.indexOf(b, i);
			if (nextB >= 0) {
				//copy all until nextB
				s.append(a.substring(i, nextB));
				i = nextB + b.length();
			}
			else {//nothing left
				s.append(a.substring(i));
				i = a.length();
			}
		}
		return s.toString();
	}

I think KMP algorithm is a good solution

Here is one correct but brute-force method in C:


#include <stdio.h>
int main()
{
char s1[100],s2[100];
printf("Enter string1:");
scanf("%s",s1);
printf("\nEnter string2:");
scanf("%s",s2);
int i,j;
int maincounter=0;
int l = strlen(s1);
char mystr[l+1];
for(i=0;i<strlen(s1);)
{
if(s1[i]==s2[0])
{
int count=1;
for(j=1;j<strlen(s2);j++)
{
if(s1[i+j]==s2[j]) count++;
}
if(count==strlen(s2)) i=i+strlen(s2);
else
{
mystr[maincounter] = s1[0];
maincounter++;
i++;
}
}
else
{
mystr[maincounter] = s1[i];
maincounter++;
i++;
}
}
mystr[maincounter] = '\0';
printf("removed = %s\n",mystr);
return 0;
}

Here is one correct but brute-force method in C:


#include <stdio.h>
int main()
{
char s1[100],s2[100];
printf("Enter string1:");
scanf("%s",s1);
printf("\nEnter string2:");
scanf("%s",s2);
int i,j;
int maincounter=0;
int l = strlen(s1);
char mystr[l+1];
for(i=0;i<strlen(s1);)
{
if(s1[i]==s2[0])
{
int count=1;
for(j=1;j<strlen(s2);j++)
{
if(s1[i+j]==s2[j]) count++;
}
if(count==strlen(s2)) i=i+strlen(s2);
else
{
mystr[maincounter] = s1[0];
maincounter++;
i++;
}
}
else
{
mystr[maincounter] = s1[i];
maincounter++;
i++;
}
}
mystr[maincounter] = '\0';
printf("removed = %s\n",mystr);
return 0;
}

bool isDetect(char* str1, char* str2){
if(len(str1)<len(str2)) return false;
for(int i=0;i<len(str2);i++){
if(str1[i]!=str2[i]) return false;
}
return true;
}

void del(char* str1, char* str2){
int cur=0;
int s=0;
while(str1[cur]){
if(isDetect(str1+cur,str2)){
cur+=len(str2);
}
else{
str1[s++]=str1[cur++];
}
}
str1[s]=str1[cur];
}

public void CheckPatternInText(string text, string pattern)
        {
            bool flag = false;
            int j = 0;
            int count = 0;
            string output = "";
            for (int i = 0; i < text.Length; i++)
            {
                output += text[i].ToString();
                if (flag)
                {
                    if (j == pattern.Length - 1 && text[i] == pattern[j])
                    {
                        count++;
                        j = 0;
                        flag = false;
                        output = output.Remove(output.Length - pattern.Length);
                    }
                    else if (text[i] == pattern[j])
                    {
                        j++;
                    }
                    else
                    {
                        j = 0;
                        flag = false;
                    }
                }
                else
                {
                    if (text[i] == pattern[j])
                    {
                        j++;
                        flag = true;
                    }
                }
            }
            Console.WriteLine(count.ToString());
            Console.WriteLine(output.ToString());
        }

int main()
{
char *s1 = "sthshetkshishekt";
char *s2 = "she";
char s3[strlen(s1)];

printf("size of s %d %d\n", sizeof(s2), strlen(s1), 0);


char *ptr1 = s1;
char *ptr2 = s2;
char *ptr3 = s3;
char *ptr4 = NULL;

while(*ptr1!='\0')
{

if(*ptr1==*ptr2)
{
ptr2++;
}
else
{
ptr2 = s2;
}

*ptr3 = *ptr1;
ptr1++;
ptr3++;

if(*ptr2 == '\0')
{
ptr4 = ptr3 - strlen(s2);
ptr3 = ptr4;
}

}

*ptr3 = '\0';

printf("s1:%s s2:%s s3:%s\n",s1, s2, s3);

}

void removePattern(String source,String pattern)
	{
		int patternHash = pattern.hashCode();
		int srcIndex= 0;
		int SRCLEN = source.length();
		String newSource ="";
		while (true)
		{
			while (  srcIndex < SRCLEN && source.charAt(srcIndex) != pattern.charAt(0) )
			{
				srcIndex ++;
			}

			if( srcIndex > SRCLEN-1 )
				break;

			String srcSubStr = source.substring(srcIndex, srcIndex+pattern.length());
			int srcHash = srcSubStr.hashCode();

			if(srcHash == patternHash)
			{
				source = source.substring(0,srcIndex) +      
                                                         source.substring(srcIndex+pattern.length());
				srcIndex = srcIndex + pattern.length();
			}
			SRCLEN = source.length();

			if( srcIndex >= SRCLEN-1 )
				break;
		}

		System.out.println("NEW STRING -->"+ source);
	}

string removeAllOcurrances(string& sa, string& sb)
{
         int new_length = sa.size();
         while (true)
         {
                 int found = sa.find(sb);
                 if (found != string::npos)
                 {
                          int k = found;
                          for (int i = found+sb.length(); i < sa.length(); i++,)
                                        sa[k++] = sa[i];
                          new_length = k;                                          
                 }
         }
         sa.resize(new_length);
         return sa;
}

void replace(char str1[], char str2[])
{
	int i = 0, j = 0;
	int len = strlen(str2);

	while(str1[i]) {
		if(strncmp(str1 + i, str2, len) == 0 ) {
			i += len;
			continue;
		}
		str1[j++] = str1[i++];
	}
	str1[j] = '\0';

f_string = "sjkthshetheshetesm"
s_string = "she"

t_string = ""

s_len = len(s_string)
s_let = 0

cur_string = ""

for x in range(0, len(f_string)):
    cur_let = f_string[x]           # Obtain the current letter

    # If the whole second string was found
    # Reset the cur string and bring index to 0 for second string
    if s_let == s_len:
        cur_string = ""
        s_let = 0

    # If the current letter is the same as the second string current letter
    # Increase index and add letter to current string
    if cur_let == s_string[s_let]:
        s_let += 1
        cur_string += cur_let
    # Else set second index to 0
    # Add the current string first and then the latest letter and reset the current string
    else:
        s_let = 0
        t_string += cur_string
        t_string += cur_let
        cur_string = ""


print t_string

Using some python code. Since python strings are immutable, I created a third string

f_string = "sjkthshetheshetesm"
s_string = "she"

t_string = ""

s_len = len(s_string)
s_let = 0

cur_string = ""

for x in range(0, len(f_string)):
    cur_let = f_string[x]           # Obtain the current letter

    # If the whole second string was found
    # Reset the cur string and bring index to 0 for second string
    if s_let == s_len:
        cur_string = ""
        s_let = 0

    # If the current letter is the same as the second string current letter
    # Increase index and add letter to current string
    if cur_let == s_string[s_let]:
        s_let += 1
        cur_string += cur_let
    # Else set second index to 0
    # Add the current string first and then the latest letter and reset the current string
    else:
        s_let = 0
        t_string += cur_string
        t_string += cur_let
        cur_string = ""


print t_string

void remove_substr(char *str, char *substr)
{
char* tmp = str;
int len = 0;

while ((tmp = strstr(tmp, substr))) {
len = strlen(tmp);
memmove(tmp, tmp+strlen(substr), (len - strlen(substr) + 1));
}
return;
}

char * removeOccurances(char *str1, char* str2)
{

//assume the chars are ascii
char hashMap[255] = {};

int i = 0;
while (str2[i] != '\0')
{

hashMap[str2[i++]] = 1;

}

int j = 0;
while(str1[j] != '\0')
{

if(hashMap[str1[j++]) == 1) //found the occurance
{
remove(str1)
}

}



}

Use Rabin Karp algorithm:

string RemovePattern(string source, string pattern)
{
   StringBuilder b = new StringBuilder();
   
   int patternLength = pattern.Length;
   int patternHash = Hash(pattern, 0, patternLength-1);   
    
   int c = 0;

   while ((c + patternLength) < source.Length)
   {
       int sourceHash = Hash(source, c, patternLength - 1);

       if ((sourceHash == patternHash)&&
           (pattern == source.SubStr(c, c + patternLength - 1))
       {
           c += patternLength;
       }
       else
       {
           builder.Append(string.CharAt(c));
           c++;
       }
   }
   return b.ToString();
}

The complexity is O(mn) where m = len(pattern), n = len(source)

In C#, it's as simple as:
String1.Replace(String2,"");