6.5 อัลกอริทึมกับสตริง

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

นับตัวอักษรแต่ละตัวด้วยอาเรย์ 26 ช่อง

บทที่ 5 นับความถี่ของตัวเลขด้วย counting array คือใช้ค่าเป็นเลขช่อง ตัวอักษรก็ทำได้เหมือนกัน เพราะ c - 'a' แปลง a ถึง z เป็นเลขช่อง 0 ถึง 25 พอดี

#include <stdio.h>
#include <ctype.h>

char line[100005];

int main()
{
    int count[26] = {0};
    fgets(line, sizeof line, stdin);
    for (int i = 0; line[i] != '\0'; i++) {
        if (isalpha(line[i])) {
            count[tolower(line[i]) - 'a']++;
        }
    }
    for (int i = 0; i < 26; i++) {
        if (count[i] > 0) {
            printf("%c %d\n", 'a' + i, count[i]);
        }
    }
    return 0;
}

Hello World

d 1
e 1
h 1
l 3
o 2
r 1
w 1

• tolower ก่อนลบ 'a' ทำให้ H กับ h ตกช่องเดียวกัน
• ช่องว่างและ '\n' ที่ fgets ติดมาไม่ผ่าน isalpha จึงไม่ต้องตัด '\n' ก่อนในโปรแกรมนี้
• ลูปที่สองไล่ช่อง 0 ถึง 25 ผลจึงเรียงตามตัวอักษรเอง และ 'a' + i แปลงเลขช่องกลับเป็นตัวอักษร

กลับคำ

ถ้าแค่ต้องพิมพ์กลับหลัง วนจากช่อง length - 1 ลงไปถึง 0 ก็พอ แต่ถ้าต้องการให้ตัวสตริงเองกลับด้าน เพื่อเอาไปใช้ต่อ ให้ใช้ index สองตัว left เริ่มจากซ้ายสุด right เริ่มจากขวาสุด สลับตัวอักษรสองช่องนั้น แล้วขยับเข้าหากันจนสวนกัน

#include <stdio.h>
#include <string.h>

char word[100005];

int main()
{
    scanf("%s", word);
    int length = strlen(word);
    int left = 0, right = length - 1;
    while (left < right) {
        char temp = word[left];
        word[left] = word[right];
        word[right] = temp;
        left++;
        right--;
    }
    printf("%s\n", word);
    return 0;
}

stressed

desserts

หลังรอบที่ 4 left เป็น 4 และ right เป็น 3 สวนกันแล้ว ลูปจึงหยุด ถ้าคำยาวคี่ สองตัวจะมาเจอกันที่ตัวกลางพอดี ซึ่งไม่ต้องสลับกับใคร เงื่อนไข left < right จัดการให้ทั้งสองกรณี

temp คือที่พักชั่วคราว ถ้าไม่มี ค่าของช่องซ้ายจะหายไปทันทีที่เขียนทับ ลองดูได้ในส่วนลองทำให้พัง

palindrome อ่านกลับหลังได้เหมือนเดิม

คำอย่าง level หรือ noon อ่านจากหลังมาหน้าได้เหมือนเดิม เรียกว่า palindrome ไม่ต้องกลับคำจริงแล้วค่อยเทียบ ใช้ตำแหน่งแบบเดียวกับการกลับคำ เทียบช่อง i กับช่อง length - 1 - i ถ้าคู่ไหนไม่เท่ากันก็ไม่ใช่ palindrome

#include <stdio.h>
#include <string.h>

char word[100005];

int main()
{
    while (scanf("%s", word) == 1) {
        int length = strlen(word);
        int is_palindrome = 1;
        for (int i = 0; i < length / 2; i++) {
            if (word[i] != word[length - 1 - i]) {
                is_palindrome = 0;
            }
        }
        if (is_palindrome) {
            printf("%s YES\n", word);
        } else {
            printf("%s NO\n", word);
        }
    }
    return 0;
}

level racecar banana noon a

level YES
racecar YES
banana NO
noon YES
a YES

วนแค่ครึ่งแรก length / 2 ก็พอ เพราะคู่ในครึ่งหลังคือคู่เดิมที่เทียบไปแล้ว คำยาวคี่อย่าง racecar มีตัวกลางคือ e ซึ่งไม่มีคู่และไม่ต้องเทียบ หาร 7 ด้วย 2 แบบจำนวนเต็มได้ 3 จึงข้ามตัวกลางไปเอง

นับคำในประโยค

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

#include <stdio.h>
#include <ctype.h>

char line[100005];

int main()
{
    fgets(line, sizeof line, stdin);
    int words = 0;
    for (int i = 0; line[i] != '\0'; i++) {
        if (!isspace(line[i]) && (i == 0 || isspace(line[i - 1]))) {
            words++;
        }
    }
    printf("%d\n", words);
    return 0;
}

  I  love   C programming

4

• isspace นับ '\n' เป็นช่องว่างด้วย จึงไม่ต้องตัด '\n' ก่อน
• ถ้า i == 0 เป็นจริง ภาษา C จะไม่ไปดู line[i - 1] เลย เพราะ || รู้ผลแล้วว่าจริง จึงไม่มีการแตะช่อง -1

ถ้าข้อมูลเข้าทั้งหมดคือประโยคนี้บรรทัดเดียว ใช้ while (scanf("%s", word) == 1) นับคำก็ได้ผลเท่ากันและสั้นกว่า เพราะ %s ข้ามช่องว่างให้เอง วิธีนับจุดเริ่มคำใช้ตอนต้องรู้ตำแหน่งของคำในบรรทัด หรือตอนข้อมูลเข้ามีหลายบรรทัดแล้วต้องนับแยกทีละบรรทัด

Caesar cipher เลื่อนตัวอักษร

รหัสลับแบบ Caesar เลื่อนตัวอักษรทุกตัวไปข้างหน้า K ตัวแบบวนรอบ ตัวพิมพ์ใหญ่ยังเป็นตัวพิมพ์ใหญ่ ตัวที่ไม่ใช่ตัวอักษรคงเดิม ท่านี้คือสูตรเลื่อนวนรอบจากหน้า 6.1 ใส่ในลูป บวกกับการรับเลขแล้วตามด้วยบรรทัดข้อความจากหน้า 6.3

#include <stdio.h>

char text[1005];

int main()
{
    int shift;
    scanf("%d", &shift);
    while (getchar() != '\n') {
    }
    fgets(text, sizeof text, stdin);
    shift = shift % 26;
    for (int i = 0; text[i] != '\0'; i++) {
        char c = text[i];
        if (c >= 'a' && c <= 'z') {
            text[i] = (c - 'a' + shift) % 26 + 'a';
        } else if (c >= 'A' && c <= 'Z') {
            text[i] = (c - 'A' + shift) % 26 + 'A';
        }
    }
    printf("%s", text);
    return 0;
}

3
Meet me at noon

Phhw ph dw qrrq

• shift % 26 ก่อนเริ่ม ทำให้ K ใหญ่แค่ไหนก็เหลือแค่ 0 ถึง 25 เลื่อน 26 ตัวคือกลับมาที่เดิม
• printf("%s", text) ไม่มี \n เพราะ text มี '\n' จาก fgets ติดมาแล้ว
• ถอดรหัสคือเลื่อนถอยหลัง K ตัว ซึ่งเท่ากับเลื่อนไปข้างหน้า 26 - K % 26 ตัว ใช้สูตรเดิมได้ ไม่ต้องยุ่งกับเลขติดลบ

run-length ย่อตัวที่ซ้ำติดกัน

ข้อความที่มีตัวซ้ำติดกันยาวๆ อย่าง aaabccdddd ย่อได้เป็นตัวอักษรตามด้วยจำนวนที่ซ้ำ ได้ a3b1c2d4 เรียกว่า run-length encoding กลุ่มตัวที่ซ้ำติดกันหนึ่งกลุ่มเรียกว่า run

#include <stdio.h>
#include <string.h>

char word[100005];

int main()
{
    scanf("%s", word);
    int length = strlen(word);
    int i = 0;
    while (i < length) {
        int j = i; // (1)!
        while (j < length && word[j] == word[i]) {
            j++;
        }
        printf("%c%d", word[i], j - i); // (2)!
        i = j; // (3)!
    }
    printf("\n");
    return 0;
}

1. i คือช่องแรกของ run ปัจจุบัน j เดินไปทางขวาตราบที่ยังเป็นตัวเดียวกับ word[i]
2. พอหยุด j อยู่ที่ช่องแรกของ run ถัดไป ความยาวของ run จึงเป็น j - i พอดี
3. กระโดดไปเริ่ม run ถัดไปที่ j เลย ไม่ต้องย้อนไปดูช่องที่นับแล้ว

aaabccdddd

a3b1c2d4

ดูเหมือนลูปซ้อนที่น่าจะช้า แต่ j เดินไปข้างหน้าอย่างเดียว และ i กระโดดตาม j ทุกช่องจึงถูกดูแค่ครั้งเดียว งานรวมคือประมาณ n ก้าว ไม่ใช่ n × n

ลองทำให้พัง

แบบที่ 1 สลับโดยไม่มีที่พัก

ในโปรแกรม reverse ตัด temp ทิ้ง เหลือสองบรรทัดนี้ในลูป

#include <stdio.h>
#include <string.h>

char word[100005];

int main()
{
    scanf("%s", word);
    int length = strlen(word);
    int left = 0, right = length - 1;
    while (left < right) {
        word[left] = word[right];
        word[right] = word[left];
        left++;
        right--;
    }
    printf("%s\n", word);
    return 0;
}

stressed

dessssed

บรรทัดที่ 12 เขียนตัวขวาทับตัวซ้ายไปแล้ว พอบรรทัดที่ 13 เอาตัวซ้ายไปใส่ช่องขวา ก็ได้ตัวขวาตัวเดิมกลับไป ครึ่งหลังของคำจึงไม่เปลี่ยน ส่วนครึ่งแรกกลายเป็นสำเนาของครึ่งหลังที่กลับด้าน คำตอบดูใกล้เคียงจนอาจไม่ทันสังเกต ทดสอบด้วยคำที่ไม่ใช่ palindrome เสมอ

แบบที่ 2 เลื่อนตัวอักษรใน char จนล้น

เขียน Caesar แบบบวกตรงๆ แล้วค่อยเช็กว่าเลย z หรือยัง ดูเหมือนถูก ลองเลื่อน y ไป 10 ตัว คำตอบที่ถูกคือ i ซึ่งมีรหัส 105

#include <stdio.h>

int main()
{
    char letter = 'y';
    letter = letter + 10;
    printf("%d\n", letter);
    if (letter > 'z') {
        letter = letter - 26;
    }
    printf("%d\n", letter);
    return 0;
}

บนเครื่องที่เขียนเอกสารนี้ได้ -125 ทั้งสองบรรทัด 'y' คือ 121 บวก 10 ได้ 131 แต่ char บนเครื่องนี้เก็บได้แค่ -128 ถึง 127 จึงล้นวนไปฝั่งติดลบ แบบเดียวกับ int ล้นในหน้า 1.3 พอเป็นค่าติดลบ เงื่อนไข letter > 'z' ก็เป็นเท็จ ไม่ได้ลบ 26 ทั้งที่ควรลบ ไม่มีคำเตือนจาก -Wall เลย

กับดักนี้เกิดเฉพาะตอนเลื่อนไกล z คือ 122 เหลือที่ก่อนถึง 127 แค่ 5 การเลื่อน 3 ตัวแบบในตัวอย่างจึงดูเหมือนใช้ได้ แล้วไปพังในชุดทดสอบที่ K ใหญ่ วิธีแก้คือใช้สูตร (c - 'a' + shift) % 26 + 'a' แบบในโปรแกรม caesar ซึ่งคำนวณเป็น int ทั้งหมด และ shift % 26 ก่อนเสมอ

สรุป

• นับตัวอักษรด้วย int count[26] และ count[c - 'a']++ ต้องแน่ใจว่า c เป็นตัวพิมพ์เล็กก่อน
• กลับคำด้วย left กับ right สลับผ่าน temp แล้วขยับเข้าหากัน
• palindrome เทียบช่อง i กับ length - 1 - i แค่ครึ่งแรก
• นับคำด้วยการนับจุดเริ่มคำ ไม่ใช่นับช่องว่าง
• Caesar ใช้ (c - 'a' + shift) % 26 + 'a' โดย shift % 26 ก่อน และอย่าบวกลงใน char ตรงๆ
• run-length ใช้ i จุดเริ่ม run กับ j ที่เดินไปข้างหน้าอย่างเดียว งานรวมแค่ n ก้าว

กลับไปเช็กรายการ ผ่านบทนี้เมื่อ แล้วไปทำแบบฝึกหัด