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!
See what happens when A = cc and B = c.
Yes, you are right. I find that I may recheck the same element in B.
so correct version should be:
Yep, it should be working right now.
Try this: A = "xyz" B = "abcde" for false positive and A = "aa" B = "aaaa" for false negative.