Kiểm tra Anagram và đếm số lần xuất hiện của Anagram trong chuỗi trên Android

Mở rộng: Đếm Anagram con (Substring Anagram)

Bài toán: Cho chuỗi text và chuỗi pattern, đếm số substring của text là anagram của pattern.

Ví dụ: text="forxxorfxdofr", pattern="for" → Kết quả: 3 (for, orf, ofr)

Triển khai

Bước 1-2: Dự án và Layout

Giống bài trước: 2 EditText + 1 Button.

Bước 3: MainActivity.java - Sliding Window Algorithm

package com.example.myapplication;

import android.os.Bundle;
import androidx.appcompat.app.AppCompatActivity;
import android.view.View;
import android.widget.EditText;
import android.widget.Toast;
import java.util.Arrays;

public class MainActivity extends AppCompatActivity {
    EditText editQuery, editPattern;

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);
        
        editQuery = findViewById(R.id.edit_query);
        editPattern = findViewById(R.id.edit_query1);

        findViewById(R.id.buttonPanel).setOnClickListener(v -> {
            String text = editQuery.getText().toString().trim();
            String pattern = editPattern.getText().toString().trim();

            if (text.isEmpty() || pattern.isEmpty()) {
                Toast.makeText(this, "Nhập đủ 2 chuỗi", Toast.LENGTH_SHORT).show();
                return;
            }

            if (areAnagrams(text, pattern)) {
                int count = countAnagramOccurrences(text, pattern);
                Toast.makeText(this, "Là Anagram. Số lần xuất hiện: " + count, Toast.LENGTH_LONG).show();
            } else {
                Toast.makeText(this, "Không phải Anagram", Toast.LENGTH_LONG).show();
            }
        });
    }

    // Kiểm tra 2 chuỗi có anagram nhau không
    private boolean areAnagrams(String s1, String s2) {
        String c1 = s1.replaceAll("\\s+", "").toLowerCase();
        String c2 = s2.replaceAll("\\s+", "").toLowerCase();
        if (c1.length() != c2.length()) return false;
        char[] a1 = c1.toCharArray();
        char[] a2 = c2.toCharArray();
        Arrays.sort(a1);
        Arrays.sort(a2);
        return Arrays.equals(a1, a2);
    }

    // Đếm substring anagram của pattern trong text - Sliding Window O(n)
    private int countAnagramOccurrences(String text, String pattern) {
        String t = text.toLowerCase();
        String p = pattern.toLowerCase();
        int n = t.length(), m = p.length();
        if (m > n) return 0;

        int[] target = new int[26];
        for (char c : p.toCharArray()) {
            if (c >= 'a' && c <= 'z') target[c - 'a']++;
        }

        int[] window = new int[26];
        int count = 0;

        // Khởi tạo window đầu tiên
        for (int i = 0; i < m; i++) {
            char c = t.charAt(i);
            if (c >= 'a' && c <= 'z') window[c - 'a']++;
        }
        if (Arrays.equals(window, target)) count++;

        // Slide window
        for (int i = m; i < n; i++) {
            char add = t.charAt(i);
            char remove = t.charAt(i - m);
            if (add >= 'a' && add <= 'z') window[add - 'a']++;
            if (remove >= 'a' && remove <= 'z') window[remove - 'a']--;
            if (Arrays.equals(window, target)) count++;
        }
        return count;
    }
}

Giải thích Sliding Window

1. Tạo mảng tần suất target[26] cho pattern
2. Tạo window kích thước = pattern.length()
3. So sánh window với target
4. Trượt window: thêm ký tự mới, bỏ ký tự cũ, so sánh lại
5. Độ phức tạp: O(n * 26) ≈ O(n)

Ví dụ chạy

Ứng dụng thực tế: Tìm từ khóa trong văn bản, bioinformatics (DNA sequence), spell check, game từ vựng.