'use client'; import React, { useState, useEffect, useRef } from 'react'; const VIEW_WIDTH = 1000; const VIEW_HEIGHT = 600; const BOX_SIZE = 50; const GAP = 10; const START_X = 50; const TEXT_Y = 180; const PATTERN_Y = 300; const NEXT_TABLE_Y = 480; // Theme Colors const COLORS = { bg: '#0f172a', primary: '#38bdf8', // Light Blue accent: '#f472b6', // Pink success: '#4ade80', // Green warning: '#fbbf24', // Amber error: '#fb7185', // Red text: '#e2e8f0', // Slate 200 dim: '#475569', // Slate 600 grid: '#1e293b' // Slate 800 }; // Data const HAYSTACK = "ABABDABACDABABCABAB"; const NEEDLE = "ABABCABAB"; // Next array (Partial Match Table) for "ABABCABAB" // Pattern: A B A B C A B A B // LPS: 0 0 1 2 0 1 2 3 4 const NEXT_ARRAY = [0, 0, 1, 2, 0, 1, 2, 3, 4]; export default function KMPAlgorithmView() { const [i, setI] = useState(0); // Index for Haystack const [j, setJ] = useState(0); // Index for Needle const [status, setStatus] = useState('IDLE'); // IDLE, COMPARING, MATCH, MISMATCH, BACKTRACK, FOUND const [log, setLog] = useState('系统就绪，准备开始...'); const [matchCount, setMatchCount] = useState(0); const [activeNextIdx, setActiveNextIdx] = useState(null); const isRunningRef = useRef(false); // Helper for delays const sleep = (ms: number) => new Promise(r => setTimeout(r, ms)); useEffect(() => { const runKMP = async () => { if (isRunningRef.current) return; isRunningRef.current = true; while (true) { // Reset state setI(0); setJ(0); setMatchCount(0); setStatus('IDLE'); setLog('初始化 KMP 算法...'); setActiveNextIdx(null); await sleep(2000); let currI = 0; let currJ = 0; while (currI < HAYSTACK.length) { // Update visual state setI(currI); setJ(currJ); setStatus('COMPARING'); setActiveNextIdx(null); setLog(`比较主串[${currI}] ('${HAYSTACK[currI]}') 与模式串[${currJ}] ('${NEEDLE[currJ]}')`); await sleep(800); if (HAYSTACK[currI] === NEEDLE[currJ]) { // Match case setStatus('MATCH'); setLog('字符匹配成功！指针后移。'); await sleep(600); currI++; currJ++; if (currJ === NEEDLE.length) { // Full pattern found setI(currI); setJ(currJ); setStatus('FOUND'); setMatchCount(prev => prev + 1); setLog(`完整匹配成功！在索引 ${currI - currJ} 处发现模式串。`); await sleep(2500); // Reset J based on Next array to continue search (like a mismatch at the hypothetical next char) // KMP logic for multiple occurrences usually involves backtracking using the LPS of the last char const nextVal = NEXT_ARRAY[currJ - 1]; setStatus('BACKTRACK'); setLog(`继续搜索... 根据 Next 表回溯 J 指针: ${currJ} -> ${nextVal}`); setActiveNextIdx(currJ - 1); currJ = nextVal; await sleep(1500); } } else { // Mismatch case setStatus('MISMATCH'); setLog('字符不匹配！'); await sleep(800); if (currJ !== 0) { // Backtrack using Next array const nextVal = NEXT_ARRAY[currJ - 1]; setStatus('BACKTRACK'); setActiveNextIdx(currJ - 1); setLog(`查询 Next 表: J=${currJ}, 前缀匹配长度为 ${nextVal}。J 回溯至 ${nextVal}。`); await sleep(1500); currJ = nextVal; // Do not increment I } else { // Start of pattern, just move I setLog('模式串首位不匹配，主串指针 I 后移。'); currI++; } } } setLog('搜索结束。正在重置...'); await sleep(3000); } }; runKMP(); }, []); // Calculate pattern visual offset // The pattern aligns visually such that pattern[j] is under haystack[i] // So pattern start X = (i - j) * (BOX_SIZE + GAP) + START_X const patternOffsetX = START_X + (i - j) * (BOX_SIZE + GAP); return ( ); }