กลิฟมายัน: หน้าต่างที่ขยับทีละหนึ่ง ควรเสียค่าตรวจแค่สองครั้ง

หน้าต่างหนึ่งอันใช้ได้เมื่อกลิฟทุกชนิดมีจำนวนเท่ากับที่ต้องการเป๊ะ เก็บตารางนับสองใบคือ need ที่นับจาก W ครั้งเดียวตอนต้น กับ have ที่นับจากหน้าต่างปัจจุบัน แล้วเลื่อนหน้าต่างทีละหนึ่ง ปรับ have แค่สองช่อง

ปัญหาที่เหลือคือคำถามว่าเท่ากันทุกช่องหรือยัง ถ้าไล่เทียบทั้ง 52 ช่องทุกก้าว ก็ยังเป็น 156 ล้าน ครั้ง ซึ่งพอไหวแต่เปลืองโดยไม่จำเป็น ทางที่คมกว่าคือเก็บตัวนับเพิ่มอีกตัวเดียวชื่อ matched แปลว่าตอนนี้มีกลิฟกี่ชนิดที่จำนวนพอดีแล้ว

ตัวนับนี้อัปเดตได้ตอนที่ค่าในช่องเปลี่ยน เพราะช่องหนึ่งช่องเปลี่ยนได้ทีละหนึ่งเท่านั้น จึงมีแค่สองจังหวะที่สำคัญ ตอนค่าขยับขึ้นมาชนพอดี ให้บวกหนึ่ง และตอนค่าขยับจากพอดีไปเกินหนึ่ง ให้ลบหนึ่ง ขาลงก็ใช้เหตุผลเดียวกันแบบกลับด้าน

int c = id(S[r]);
have[c]++;
if (have[c] == need[c]) matched++;              // ชนิดนี้เพิ่งพอดี
else if (have[c] == need[c] + 1) matched--;     // เพิ่งเกิน เลยหลุดจากคำว่าพอดี

if (r >= g) {                                    // ตัวที่หลุดออกทางซ้าย
    int d = id(S[r - g]);
    if (have[d] == need[d]) matched--;
    else if (have[d] == need[d] + 1) matched++;
    have[d]--;
}
if (r >= g - 1 && matched == distinct) ans++;    // ทุกชนิดพอดีพร้อมกัน

หน้าต่างใช้ได้เมื่อ matched เท่ากับจำนวนชนิดที่ปรากฏใน W ไม่ใช่ 52 เพราะชนิดที่ W ไม่ได้ใช้เลยมี need เป็นศูนย์ และมันก็ถูกนับว่าพอดีตั้งแต่ยังไม่เจอตัวไหนเลย

จุดนี้คือกับดักที่ทำให้โค้ดตอบผิดได้ง่ายที่สุด ถ้าเผลอไปเทียบกับ 52 โปรแกรมจะไม่มีวันเจอหน้าต่างที่ใช้ได้เลยสักอัน ส่วนถ้าลืมกรณีเกินหนึ่ง ตัวนับจะค้างอยู่ที่พอดี ทั้งที่กลิฟชนิดนั้นล้นออกมาแล้ว

คำที่ตามหาคือ cAda ซึ่งใช้กลิฟ 4 ชนิด ดังนั้นหน้าต่างจะใช้ได้เมื่อ matched ขึ้นไปแตะ 4 พอดี

ทุกก้าวแตะข้อมูลแค่สองช่อง คือช่องของตัวที่เข้าและช่องของตัวที่ออก ค่า matched จึงเดินขึ้นลงเองโดยไม่ต้องกวาดตารางทั้งใบเลยสักครั้ง

สังเกตว่าแนวคิดแรกไม่ได้แพงเพราะ |S| ใหญ่ แต่แพงเพราะมันเอา g มาคูณกับความยาวของแผ่นจารึก ทั้งที่ g ตัวนั้นเป็นตัวเดิมที่เพิ่งนับไปเมื่อก้าวที่แล้ว

ถ้าอยากเห็นท่าหน้าต่างเลื่อนแบบเต็ม ๆ ตั้งแต่ต้น รวมถึงเวอร์ชันที่ความยาวหน้าต่างไม่คงที่ ไปอ่านบทปูพื้นฐาน สองตัวชี้กับหน้าต่างเลื่อน ก่อนได้

แผ่นจารึกยาวสามล้านตัว จึงอ่านเข้ามาเป็นสตริงเดียวทีเดียว และเดินผ่านมันรอบเดียวจบ ตารางนับใช้ int ขนาด 52 ช่อง สองใบ กินหน่วยความจำไม่ถึงครึ่งกิโลไบต์

#include <bits/stdc++.h>
using namespace std;
static inline int idx(char c){ return c>='a'&&c<='z' ? c-'a' : c-'A'+26; }
int main(){
    int g; long long n;
    if(scanf("%d %lld",&g,&n)!=2) return 0;
    static char W[3005]; scanf("%s",W);
    string S; { S.resize(n+5); scanf("%s",&S[0]); S.resize(strlen(S.c_str())); }
    int need[52]={0}, have[52]={0};
    for(int i=0;i<g;i++) need[idx(W[i])]++;
    int distinct=0; for(int i=0;i<52;i++) if(need[i]) distinct++;
    int matched=0; long long ans=0; int L=(int)S.size();
    for(int r=0;r<L;r++){
        int c=idx(S[r]);
        have[c]++; if(have[c]==need[c]) matched++; else if(have[c]==need[c]+1) matched--;
        if(r>=g){ int d=idx(S[r-g]); if(have[d]==need[d]) matched--; else if(have[d]==need[d]+1) matched++; have[d]--; }
        if(r>=g-1 && matched==distinct) ans++;
    }
    printf("%lld\n",ans);
}

// ตัวตรวจสอบแบบซื่อ ๆ นับใหม่ทุกหน้าต่าง ใช้ได้แค่อินพุตเล็ก ๆ ตอนสุ่มเทียบก่อนส่ง
#include <bits/stdc++.h>
using namespace std;
static int id(char c){ return c>='a'&&c<='z' ? c-'a' : c-'A'+26; }
int main(){
    int g; long long n; scanf("%d %lld",&g,&n);
    static char W[3005], S[3000006];
    scanf("%s %s",W,S);
    int need[52]={0};
    for(int i=0;i<g;i++) need[id(W[i])]++;
    int L=(int)strlen(S), ans=0;
    for(int i=0;i+g<=L;i++){
        int c[52]={0};
        for(int j=0;j<g;j++) c[id(S[i+j])]++;
        bool ok=true;
        for(int t=0;t<52;t++) if(c[t]!=need[t]){ ok=false; break; }
        if(ok) ans++;
    }
    printf("%d\n",ans);
}

เวลาที่วัดได้บนเครื่องผม อินพุตเต็มขอบเขตคือแผ่นจารึกสามล้านตัวกับคำยาวสามพันตัว ใช้เวลา 96 มิลลิวินาที จากลิมิตสามวินาที

เวลาจะยกท่านี้ไปข้ออื่น มีคำถามเดียวที่ต้องตอบก่อน คือของที่เราเก็บไว้นั้น ซ่อมจากส่วนต่างได้ไหม เมื่อรู้แค่ว่าใครเข้าและใครออก จำนวนนับกับผลรวมซ่อมได้ เพราะตัวที่ออกไปหักออกตรง ๆ ได้ ส่วนค่ามากสุดของหน้าต่างซ่อมไม่ได้ เพราะวันที่ตัวออกคือตัวที่มากที่สุดพอดี ไม่มีใครรู้ว่าตัวรองคือตัวไหนโดยไม่กวาดหน้าต่างใหม่ ถ้าเจอกรณีหลัง ให้เลิกดัดวิธีนับแล้วไปเปลี่ยนเครื่องมือเลย ท่าที่ใช้แทนอยู่ในหัวข้อสุดท้ายของบทปูพื้นฐาน สองตัวชี้กับหน้าต่างเลื่อน