How to check the top 2 objects? It seem we can only look at the top
object.
Another question is we have to check N-1 chars from the top of the
stack, where N is the length of the str2. If there are multiple
characters in str2 that are the same as its last char (e.g. accccbc),
then even if str1 is the same as string 2, we have to do extra check 4
times whenever we meet a 'c' in str1.
My idea is to have a companion array recording the maximum matched index
of the char sequence in str1. If there is a total match of str2, remove
it, continue with the next character. Since we recorded the max matched
index of previous char sequence in str1, we can continue the matching
and so on so forth. If there is a mismatch of current character, reset
the array because there won't be any matching of all the previous char
sequence with this mismatched char.
Below is the code. For convenience, used a stack to hold the char seq,
and the output is in reverse order. But the main idea is presented.
#include
#include
#include
using namespace std;
int main()
{
string str1, str2;
cout << "Enter string 1:";
getline(cin, str1);
cout << "Enter string 2:";
getline(cin, str2);
int len1=str1.length();
int len2=str2.length();
// str1 is empty.
if(len1==0) return 0;
//str2 is empty or str1 is shorter than str2.
if((len2==0)||(len1
int *pMatchArray=new int[len1/len2];
for (int i = 0; i*(pMatchArray+i) = -1;
int last = 0; // last active item in array, record matching of
current char sequence
int j=0; // index used in str2
stack schar;
for(int i=0; i{
schar.push(str1[i]);
if(str1[i] == str2[j])
{
(*(pMatchArray+last))++;
if((++j)==len2) //match found for whole str2
{
//remove str2 from current pos;
for(int itmp=0; itmpschar.pop();
*(pMatchArray+last) = -1;
if (last == 0)
j=0;
else
{
j = *(pMatchArray+(--last));
j++;
}
}
}
else if(str1[i] == str2[0])
{
last++;
*(pMatchArray+last) = 0;
j=1;
}
else
{
while(last>=0)
*(pMatchArray+(last--)) = 0;
last = 0;
j = 0;
}
}
while(!schar.empty())
{
cout << schar.top();
schar.pop();
}
return 0;
}
