Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Блог пользователя DNNJFM

why I can't find subarray correctly?
Автор DNNJFM, история, 8 лет назад, По-английски

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!

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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;
    → Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить