DNNJFM's blog

why I can't find subarray correctly?
By DNNJFM, history, 8 years ago, In English

To clarify, "subarray" is defined like, for example:

if A="abc" B="??a???b????c???" then A is subarray of B.

I have two version to check if A is subarray of B, but versionI get AC, versionII get WA:

version I. iterate the bigger string B.

curA=0;
for(int i=0;i<B.size;i++){
    c=B[i];
    if(curA<A.size && A[curA]==c )curA++;
}
if(curA==A.size)return true;
else return false;

version II. iterate the smaller string A

curB=0;
for(int i=0;i<A.size;i++){
    c=A[i];
    while(curB<B.size && B[curB]!=c ) curB++;
    if(curB==B.size)return false;
}
return true;

**** Why versionI is correct, while versionII is wrong? anyone please explain or give an example to show that versionII is wrong, sincerly thanks in advace!

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

See what happens when A = cc and B = c.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, you are right. I find that I may recheck the same element in B.

    so correct version should be:

    curB=0;
for(int i=0;i<A.size;i++){
    c=A[i];
    while(curB<B.size && B[curB]!=c ) curB++;
    if(curB==B.size)return false;
    curB++;//move to next element to avoid recheck.
}
return true;
    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Try this: A = "xyz" B = "abcde" for false positive and A = "aa" B = "aaaa" for false negative.

→ Reply