subSequence

[poloblue]

Good Afternoon,

I'm having trouble with a school assignment. The assignment entails:

Write the implementation of the function subsequence for the orderedArrayListType class. Also write a program to test your function.

Prototype:
bool orderedArrayListType::subSequence (orderedArrayListType &S,orderedArrayListType &L);

Definition: subsequence returns true if S is a subsequence of L, false otherwise. Where S is a subsequence of L if for every pair of elements x and y in S at positions i and j, respectively, i < j, and also are in L at positions k and l, respectively, then k < l.

So far I have this:

bool orderedArrayListType::subSequence(orderedArrayListType &S, orderedArrayListType &L)  

02 {  
     string X, Y;
03      if (Y.length() > X.length())  

04         swap(X,Y);  

05      int S = X.length(),L=Y.length();  

06      vector< vector<int> > c(2, vector<int>(L+1,0));  

07      int i,j;  

08      for (i=1;i<=S;i++)  

09      {  

10          for (j=1;j<=L;j++)  

11          {  

12              if (X[i-1]==Y[j-1])  

13                 c[1][j]=c[0][j-1]+1;  

14              else 

15                  c[1][j]=max(c[1][j-1],c[0][j]);  

16          }  

17          for (j=1;j<=L;j++)  

18              c[0][j]=c[1][j];  

19      }  

20      return (c[1][L]);

[rubberman]

This is just another name for substring search. Again what I keep saying to you programming newbies - understand clearly first what your task is and then write out what you need to do in plain language pseudo-code each step that you need to take to accomplish your task. Design first, code last.

Example: I had to develop a rule processing engine where customers could edit some specifications in the database, and it would adapt our compiled software (C++ code) to their site requirements. I first wrote out as clearly as I could what we needed to do. Then I designed UML models until I had a perfectly clear picture in my mind how the system was structured and how the data flows and transformations (including generating complex SQL query code) had to work. That took several months of intense work (mostly brain work). Coding and testing took two weeks. I got a patent for the work... In any case, complex manufacturing process changes could be done with editing less than a half dozen rules stored in the database. My program would read those rules, modify our classes internal structures as necessary, generate the appropriate (and optimized) SQL code to do things like route a lot (semiconductor wafers in this case) to the best next piece of equipment in the fab based upon the lot's process plan, the available equipment, recipes loaded in the equipment, maintenance plans for the equipment, priority of the lot, and a zillion other factors (just one example of using the rule engine). What used to take 3 pages of complex custom C++ code was reduced to 6 simple rules in the database executed by one line of C++ code. That line never changed. If the rules needed to be changed, then the manufacturing engineers could do that, and send a message to the servers to reload the rule set. Bingo - no down time and no programming required.

Analysis of the generated SQL code by the rule engine showed that we could automatically generate very much optimized database queries that ran significantly faster than those manually written by database experts to accomplish the same task.

The point I'm trying to get across is that no matter how complicated the problem seems, working it out in your head, on paper, or whatever - what Einstein called his verdanken (virtual or mental) experiments - will help you solve those problems in the most expeditious manner.

[rubberman]

So, putting my babbling aside, here is some simple pseudo-code for a substring search (not using the strstr() function) - and I am going to assume that the orderedArrayListType class has an array index operator - makes things a lot easier. :-)

S = subset (possibly)
L = list

current member of L is called cl
current member of S is called cs

// Outer loop
found = false
for cl = 0, while not found and cl < L.length(), cl = cl + 1
    // Check if S matches L at current position in L
    // Set placeholder true or false depending upon whether S.length() + cl
    // is past the end of L. If so, then we are done.
    // If the logic tests false, then the inner loop will be skipped and
    // we are done.
    maybe_found = (L.length() >= cl + S.length())
    for cs = 0, while maybe_found and cs < S.length(), cs = cs + 1
        if L[cl + cs] != S[cs]
            cl = cl + cs        // Need to adjust cl for number of elements in S we tested
            maybe_found = false
        end if
    end for
    found = maybe_found         // If maybe_found is still set, we are done.
end for
return found

Anyway, my point is that is is a generic search algorithm that can be adapted easily to your problem.

[poloblue]

So, putting my babbling aside, here is some simple pseudo-code for a substring search (not using the strstr() function) - and I am going to assume that the orderedArrayListType class has an array index operator - makes things a lot easier. :-)

S = subset (possibly)
L = list

current member of L is called cl
current member of S is called cs

// Outer loop
found = false
for cl = 0, while not found and cl < L.length(), cl = cl + 1
    // Check if S matches L at current position in L
    // Set placeholder true or false depending upon whether S.length() + cl
    // is past the end of L. If so, then we are done.
    // If the logic tests false, then the inner loop will be skipped and
    // we are done.
    maybe_found = (L.length() >= cl + S.length())
    for cs = 0, while maybe_found and cs < S.length(), cs = cs + 1
        if L[cl + cs] != S[cs]
            cl = cl + cs        // Need to adjust cl for number of elements in S we tested
            maybe_found = false
        end if
    end for
    found = maybe_found         // If maybe_found is still set, we are done.
end for
return found

Anyway, my point is that is is a generic search algorithm that can be adapted easily to your problem.

Thank you, rubberman for your help, I really appreciate your input.