%&<<&Search & replace %&<<&#define Expr, AsciiSet \def\tascii{ {\it ascii \def\tAsciiSet{ {\it AsciiSet \def\tExpr{ {\it Expr %&>>&3 0 3 8 %&<<&Task ÅπßΓ∞ ¼δ αáí«ΓáѼ ß á½Σáó¿Γ«¼ $\Sigma=\{ \alpha_0, ... , \alpha_{\sigma-1\$ ñ½¿¡δ $\sigma$ (ó ß½πτáÑ ¿ß»«½∞º«óá¡¿∩ ¬«ñ¿α«ó¬¿ ASCII $\sigma=256$ ) ê¼Ñ∩ ΓѬßΓ $T=t_1t_2.....t_\theta$, ∩ó½∩εΘ¿⌐ß∩ ó «íΘѼ ß½πτáÑ ñ«ßΓáΓ«τ¡« »α«¿ºó«½∞¡«⌐ »«ß½Ññ«óáΓѽ∞¡«ßΓ∞ε ß¿¼ó«½«ó ¿º á½Σáó¿Γá $\Sigma$ ¿ µÑ»«τ¬¿ ß¿¼ó«½«ó $P_i=p_{i1...p_{il$, ∩ó½∩εΘ¿Ñß∩ »«ñ»«ß½Ññ«óáΓѽ∞¡«ßΓ∩¼¿ ó $T$, ¡á¼ ¡Ñ«íσ«ñ¿¼« ¡áσ«ñ¿Γ∞ óßÑ óσ«ªñÑ¡¿∩ $P_i$ ó $T$. ¡« «í«íΘ¿Γ∞ ñá¡¡πε ºáñáτπ ñ« ß½ÑñπεΘ¿σ: 1)~Ä»¿ßáΓ∞ ∩ºδ¬, »«ºó«½∩εΘ¿⌐ ó ñ«ßΓáΓ«τ¡« «íΘѼ ó¿ñÑ ºáñáóáΓ∞ $P_i$ ó ó¿ñÑ Φáí½«¡«ó ñ½∩ »«¿ß¬á. 2)~ÅαÑñ½«ª¿Γ∞ á½ú«α¿Γ¼ »«¿ß¬á ó $T$ óδαáªÑ¡¿⌐, ß««ΓóÑΓßΓóπεΘ¿σ Φáí½«¡á¼.

%&>>&0 0 0 0 %&<<&alphabet descr. ū߬«½∞¬π ¼δ αáß»«½áúáѼ Γ«½∞¬« á½Σáó¿Γ«¼ $\Sigma$, á ñ½∩ «»¿ßá¡¿∩ ∩ºδ¬á ¡Ñ«íσ«ñ¿¼« ¡á½¿τ¿Ñ ¼¡«ªÑßΓóá ¼ÑΓáß¿¼ó«½«ó, Γ« ¡á¼ »α¿ñÑΓß∩ «íΩ∩ó¿Γ∞ ¡Ñ¬«Γ«αδÑ ß¿¼ó«½δ ¿º á½Σáó¿Γá ”ß½πªÑí¡δ¼¿”, á ñ½∩ ¿σ »αÑñßΓáó½Ñ¡¿∩ »«½∞º«óáΓ∞ß∩ ¬«¼í¿¡áµ¿∩¼¿ ß½πªÑí¡δσ ß¿¼ó«½«ó. é ß½πτáÑ, ¬«úñá á½Σáó¿Γ«¼ ∩ó½∩ÑΓß∩ ASCII φΓπ ºáñáτπ ¼«ª¡« αÑΦ¿Γ∞ ¡á»α¿¼Ñα ß½ÑñπεΘ¿¼ «íαẫ¼: ߻ѵ¿á½∞¡δÑ ß¿¼ó«½δ – {\it SpecialChars\tt = $\{$’[’, ’]’, ’(’, ’)’, ’$\{$’, ’$\$’, ’\char124’, ’-’, ’\char94’, ’\char92’, ’?’, ’\#’$\$. ä½∩ »αÑñßΓáó½Ñ¡¿∩ ߻ѵ¿á½∞¡δσ ß¿¼ó«½«ó ñ«½ª¡á ßπΘÑßΓó«óáΓ∞ 󫺼«ª¡«ßΓ∞ ó¼ÑßΓ« ½εí«ú« ß¿¼ó«½á $\alpha_{NN$ óóÑßΓ¿ {\tt\BSL xNN, úñÑ {\tt NN – ¬«ñ ß¿¼ó«½á (»«α∩ñ¬«óδ⌐ ¡«¼Ñα ó á½Σáó¿ΓÑ).

%&>>&9 0 9 8 %&<<&AsciiSet description éóÑñѼ »«¡∩Γ¿Ñ \tAsciiSet – φΓ« τáßΓ∞ Φáí½«¡á, «»αÑñѽ∩εΘá∩ ¼¡«ªÑßΓó« ß¿¼ó«½«ó, ñ«»πßΓ¿¼δσ ó «ñ¡«⌐ »«º¿µ¿¿. ¥Γ« ¿½¿ «ñ¿¡ ß¿¼ó«½ ¿º $\Sigma \backslash SpecialChars$, ¿½¿ {\tt ’?’ – τΓ« «º¡áτÑÑΓ ó«º¼«ª¡«ßΓ∞ »«∩ó½Ñ¡¿∩ ½εí«ú« ß¿¼ó«½á á½Σáó¿Γá ó ñá¡«⌐ »«º¿µ¿¿, ¿½¿ ºá¬½ετÑ¡«Ñ ó ¬óáñαáΓ¡δÑ ß¬«í¬¿ óδαáªÑ¡¿Ñ, «»αÑñѽ∩εΘÑÑ ¼¡«ªÑßΓó« ñ«»πßΓ¿¼δσ ß¿¼ó«½«ó ({\tt[$\alpha_i$-$\alpha_j$] – ½εí«⌐ ß¿¼ó«½ «Γ $\alpha_i$ ñ« $\alpha_j$ , {\tt[$\alpha_{i_1...\alpha_{i_k$] – ½εí«⌐ ß¿¼ó«½ ¿º ¼¡«ªÑßΓóá $\alpha_{i_1...\alpha_{i_k$ , {\tt[\char94 $M$] – ½εí«⌐ ß¿¼ó«½ ¿º $\Sigma \backslash M$ ).

Åα¿¼Ñα 1) {\tt’a’ – ñ«»πßΓ¿¼ «ñ¿¡ ß¿¼ó«½. Åα¿¼Ñα 2) {\tt’[a-p]’ – ñ«»πßΓ¿¼ ½εí«⌐ ß¿¼ó«½ «Γ {\tt’a’ ñ« {\tt’p’. Åα¿¼Ñα 3) {\tt’[acxv]’ – ñ«»πßΓ¿¼ ½εí«⌐ ß¿¼ó«½ ¿º ¼¡«ªÑßΓóá {\tt$\{$’a’,’c’,’x’,’v’$\$. Åα¿¼Ñα 4) {\tt’[\char94ac-f]’ – ñ«»πßΓ¿¼ ½εí«⌐ ß¿¼ó«½, ¬α«¼Ñ ß¿¼ó«½«ó {\tt$\{$’a’,’c’,’d’,’e’,’f’$\$.

%&>>&F 0 F 10 %&<<&Expr description äá½ÑÑ ß½ÑñπÑΓ αáßß¼«ΓαÑΓ∞ »«ß½Ññ«óáΓѽ∞¡«ßΓ¿ \tAsciiSet ¿ ¿º ¡¿σ ¬«¡ßΓαπ¿α«óáΓ∞ Φáí½«¡δ \tExpr~ ß ¿ß»«½∞º«ó᡿Ѽ ß½ÑñπεΘ¿σ »αáó¿½: »α¿ ¡á½¿τ¿¿ ¡Ñ߬«½∞¬¿σ óδαáªÑ¡¿⌐ $e_1,...,e_i$ ºá»¿ß∞ {\tt ($e_1$ \char124 ... \char124 $e_i$) «º¡áτáÑΓ ñ«»πßΓ¿¼«ßΓ∞ ½εí«ú« ¿º ñá¡¡δσ óδαáªÑ¡¿⌐. {\tt$\{$$expr$$\$ «º¡áτáÑΓ, τΓ« $expr$ ¼«ªÑΓ »«óΓ«α∩Γ∞ß∩ $\ge0$ αáº. ä½∩ »«ñ«í¡δσ úαá¼¼áΓ¿τÑ߬¿σ ¬«¡ßΓαπ¬µ¿⌐ ñ«»πßΓ¿¼á 󽫪ѡ¡«ßΓ∞.

%&>>&5 0 5 8 %&<<&Expressions specification // grammar definition Åα¿óÑñÑ¡¡«Ñ óδΦÑ ¡ÑΣ«α¼á½∞¡«Ñ «»¿ßá¡¿Ñ ∩ºδ¬á Φáí½«¡«ó ¼«ª¡« Σ«α¼á½¿º«óáΓ∞, π¬áºáó ¼Ñσá¡¿º¼ »«α«ªñÑ¡¿∩ Φáí½«¡«ó Γ.Ñ. úαá¼¼áΓ¿¬π.

{\tt %&<<&temporary defines \def\tmexa{ {\it e1 \def\tmexb{ {\it Chain

%&>>&1 0 1 11 \halign{ #\quad & \hfil # &\quad#\hfill &;{\rm # \hfil\cr \tascii & = \hfill & {\rm ½εí«⌐ ß¿¼ó«½ ¿º $\Sigma$ & ¬α«¼Ñ ߻ѵ¿á½∞¡δσ \cr & \char124 & \BSL xNN & {\tt NN ΦÑßΓ¡áñµáΓÑα¿τ¡δ⌐ ¬«ñ ß¿¼ó«½á \cr \noalign{\vskip 5pt \tmexa & = \hfill & \tascii & \cr & \char124 & \tmexa\tascii & \cr & \char124 & \tmexa\tascii-\tascii & \cr \noalign{\vskip 5pt \tAsciiSet & = \hfill & \tascii & \cr & \char124 & [\tmexa] & «ñ¿¡ ¿º ß¿¼ó«½«ó \tmexa \cr & \char124 & [\char94\tmexa] & ½εí«⌐ ß¿¼ó«½ ¿º $\Sigma$ ¬α«¼Ñ \tmexa \cr \noalign{\vskip 5pt \tmexb & = \hfill & nothing & «»αÑñѽ∩ÑΓß∩ µÑ»«τ¬á ¿º \tAsciiSet \cr & \char124 & \tAsciiSet & \cr & \char124 & \tmexb \tAsciiSet & \cr \noalign{\vskip 5pt \tExpr & = \hfill & \tmexb & \cr & \char124 & (\tExpr\char124\tExpr\char124...\char124\tExpr) & «ñ¡« ¿º óδαáªÑ¡¿⌐ \cr & \char124 & $\{$\tExpr$\$ & »«óΓ«α óδαáªÑ¡¿∩ $\ge0$ αẠ\cr

Åα¿¼Ñα \tExpr: {\tt Pa$\{$t$\$[eo]rn . äá¡¡«¼π Φáí½«¡π πñ«ó½ÑΓó«α∩εΓ ¡á»α¿¼Ñα ß½ÑñπεΘ¿Ñ »«ß½Ññ«óáΓѽ∞¡«ßΓ¿ ß¿¼ó«½«ó: {\tt’Paorn’ , ’Paern’ , ’Pattttttttorn’ , ’Pattern’

%&>>&8 0 3 1E \def\tAut{ { $\frak S$ \vskip 5pt %&<<&task–>automat ÆÑ»Ñα∞ »ÑαÑ⌐ñѼ ¬ αáßß¼«ΓαÑ¡¿ε óΓ«α«ú« ó«»α«ßá. ÅπßΓ∞ ¼δ ¿¼ÑѼ Φáí½«¡ \tExpr ¿ σ«Γ¿¼ ¡á⌐Γ¿ ó ΓѬßΓÑ »«ß½Ññ«óáΓѽ∞¡«ßΓ¿ ß¿¼ó«½«ó, πñ«ó½ÑΓó«α∩εΘ¿Ñ ñá¡¡«¼π Φáí½«¡π. ä½∩ αÑΦÑ¡¿∩ φΓ«⌐ ºáñáτ¿ ¡Ñ«íσ«ñ¿¼« »«ßΓα«¿Γ∞ ¬«¡Ñτ¡δ⌐ áóΓ«¼áΓ, ß««ΓóÑΓßΓóπεΘ¿⌐ Φáí½«¡π \tExpr. \tExpr ß«ßΓ«¿Γ ¿º »«ß½Ññ«óáΓѽ∞¡«ßΓ¿ \tAsciiSet : $A_0,...,A_{n-1$ αáºñѽѡ¡δσ ߻ѵ¿á½∞¡δ¼¿ ß¿¼ó«½á¼¿. ÅαÑñ½áúáÑΓß∩ αáßß¼«ΓαÑΓ∞ ¬«¡Ñτ¡δ⌐ áóΓ«¼áΓ \tAut ß $n+1$ ß«ßΓ«∩¡¿∩¼¿ $S_{-1,S_0,...,S_{n-1$ , úñÑ $S_{-1$ - ¡áτá½∞¡«Ñ ß«ßΓ«∩¡¿Ñ áóΓ«¼áΓá (óσ«ñ). ÅÑαÑσ«ñδ ¼Ñªñπ ß«ßΓ«∩¡¿∩¼¿ ó áóΓ«¼áΓÑ «»αÑñѽ∩εΓß∩ ß½ÑñπεΘ¿¼ «íαẫ¼: Ñß½¿ »«ß½Ñ $A_i$ ¼«ªÑΓ ß½Ññ«óáΓ∞ $A_j$, Γ« ó áóΓ«¼áΓÑ ñ«»πßΓ¿¼ »ÑαÑσ«ñ «Γ $S_i$ ¬ $S_j$

%&>>&1 0 1 0 \def\vAsciiMask{{\it AsciiMask \def\vTableMask{{\it TableMask %&<<&TabkeMask definition èáªñ«¼π $i-$¼π ß«ßΓ«∩¡¿ε ßΓáó¿¼ ó ß««ΓóÑΓßΓó¿Ñ í¿Γ«óπε ¼á߬π \vTableMask[$i$] ñ½¿¡δ $n+1$ Γá¬πε τΓ« Ñß½¿ $j-$⌐ í¿Γ αáóÑ¡ $1$, Γ« »ÑαÑσ«ñ «Γ $S_i$ ¬ $S_j$ 󫺼«ªÑ¡, ¿¡áτÑ ¡Ñ󫺼«ªÑ¡. îá߬á, ß««ΓóÑΓßΓóπεΘá∩ $S_{-1$, ñáÑΓ ¡á¼ Γ«τ¬¿ óσ«ñá áóΓ«¼áΓá \tAut . Æᬿ¼ «íαẫ¼ ¼δ »«½πτáѼ ¼áΓα¿µπ $(n+1) \times (n+1)$, ß«ßΓ«∩Θπε ¿º $0$ ¿ $1$ , ¬«Γ«αá∩ «ñ¡«º¡áτ¡« ºáñáÑΓ \tAut.

%&>>&0 0 0 4 %&<<&AsciiMask definition ū߬«½∞¬π ñ½∩ »α«¿ºó«½∞¡«ú« \tAsciiSet ñ«»πßΓ¿¼δ¼¿ ¼«úπΓ ∩ó½∩Γ∞ß∩ ¡Ñ߬«½∞¬« ß¿¼ó«½«ó, Γ« ¡á¼ »α¿ñÑΓß∩ ¬áªñ«¼π $\alpha_i$ »«ßΓáó¿Γ∞ ó ß««ΓóÑΓßΓó¿Ñ í¿Γ«óπε ¼á߬π \vAsciiMask[$i$] ñ½¿¡δ $n+1$ , «»αÑñѽ∩Ѽπε ß½ÑñπεΘ¿¼ «íαẫ¼: $j-$⌐ í¿Γ ¼á߬¿, ß««ΓóÑΓßΓóπεΘÑ⌐ $\alpha_i$, αáóÑ¡ 1 Γ«úñá ¿ Γ«½∞¬« Γ«úñá, ¬«úñá $j-$⌐ \tAsciiSet ñ«»π߬áÑΓ ß¿¼ó«½ $\alpha_i$.

%&>>&3 0 3 4D %&<<&ǽú«α¿Γ¼ ä½∩ ¡áσ«ªñÑ¡¿∩ Σαáú¼Ñ¡Γá ΓѬßΓá, ß««ΓóÑΓßΓóπεΘÑú« Φáí½«¡π ¼«ª¡« ó«ß»«½∞º«óáΓ∞ß∩ á½ú«α¿Γ¼«¼, »α¿óÑñÑ¡¡δ¼ ºñÑß∞ ó ß¿¡Γá¬ß¿ßÑ, í½¿º¬«¼ ¬ ß¿¡Γá¬ß¿ßπ ∩ºδ¬á C++.

%&<<&#defines ñ½∩ á½ú«α¿Γ¼«ó \def\ppwhile{{\bf while \def\ppfor{{\bf for \def\ppif{{\bf if \def\ppelse{{\bf else \def\vCur{{\it~Cur \def\vTmp{{\it~Tmp %&>>&0 0 0 1

\vskip 15 pt \vbox {\tt \+ \vCur = \vTableMask [0] ; \cr \+ \ppwhile & ( *$T$!=0 \&\& \vCur[$n$]==0 ) \cr \+& $\{$ \cr \+& \vCur \&= \vAsciiMask[*$T$++]; \cr \+& \vTmp = \vTableMask [0] ; \cr \+& \ppfor & ($i$=0 ; $i$ < $n$ ; $i$ ++) \cr \+&& \ppif & ( \vCur [$i$] != 0) \cr \+&&& \vTmp \char124= \vTableMask [$i$+1] ; \cr \+& \vCur =$Tmp$ ; \cr \+& $\$ \cr

é á½ú«α¿Γ¼Ñ $Tmp$, $Cur$ í¿Γ«óδÑ ¼á߬¿. û¿¬½ αáí«ΓáÑΓ ñ« ΓÑσ »«α, »«¬á ¡Ñ ¬«¡τ¿½ß∩ ΓѬßΓ $T$ ¿½¿ »«¬á ¡Ñ óßΓαÑΓ¿½«ß∞ ß««ΓóÑΓßΓó¿Ñ ΓѬßΓá Φáí½«¡π. àß½¿ $i-$⌐ í¿Γ ¼á߬¿ $Cur$ αáóÑ¡ 1, Γ« φΓ« º¡áτ¿Γ, τΓ« ó ñá¡¡δ⌐ ¼«¼Ñ¡Γ áóΓ«¼áΓ \tAut ¼«ñÑΓ ¡áσ«ñ¿Γ∞ß∩ ó ß«ßΓ«∩¡¿¿ $i$ ¿ ΓѬπΘ¿⌐ ß¿¼ó«½ ΓѬßΓá ¼«ªÑΓ »α¿¡áñ½ÑªáΓ∞ $i-$¼π \tAsciiSet. Æᬿ¼ «íαẫ¼ αáóÑ¡ßΓó« »«ß½Ññ¡Ñú« í¿Γá ¼á߬¿ $Cur$ Ññ¿¡¿µÑ «º¡áτáÑΓ ¡á⌐ñÑ¡¡«Ñ ß««ΓóÑΓßΓó¿Ñ (¡á⌐ñÑ¡ ¬«¡Ñµ ß««ΓóÑΓßΓó¿∩). é í«½∞Φ¿¡ßΓóÑ ß½πτáÑó ¡Ñ«íσ«ñ¿¼« ¡á⌐Γ¿ ¡áτὫ Σαáú¼Ñ¡Γá ¿½¿ πº¡áΓ∞ Ñú« ñ½¿¡π. ä½∩ φΓ«ú«, ¡á»α¿¼Ñα, ¼«ª¡« ”αáºóÑα¡πΓ∞” Φáí½«¡ ¿ ºá»πßΓ¿Γ∞ á½ú«α¿Γ¼ ó «íαáΓ¡πε ßΓ«α«¡π »« ΓѬßΓπ.

¡« »«ßΓα«¿Γ∞ «µÑ¡¬π ßóÑασπ ¡á ¬«½¿τÑßΓó« φ½Ñ¼Ñ¡Γáα¡δσ «»Ñαᵿ⌐, ΓαÑíπѼδσ ñ½∩ αÑ὿ºáµ¿¿ «ñ¡«ú« Φáúá á½ú«α¿Γ¼á. àß½¿ $\varphi(n)$ – Γαπñ«Ñ¼¬«ßΓ∞ «ñ¡«⌐ «»Ñαᵿ¿ ß í¿Γ«ó«⌐ ¼á߬«⌐ {\tt =, \&=, \char124= , Γ« «µÑ¡¬á ßóÑασπ ¡á Γαπñ«Ñ¼¬«ßΓ∞ «ñ¡«ú« Φáúá ñá¡¡«ú« á½ú«α¿Γ¼á íπñÑΓ αáó¡á $O(n \times \varphi(n))$.

%&>>&A 0 0 A %&<<&ǽú«α¿Γ¼ ß »α«ßΓ«⌐ «»Γ¿¼¿ºáµ¿Ñ⌐ àß½¿ ó ¬«¡Ñτ¡«¼ áóΓ«¼áΓÑ \tAut ßπΘÑßΓóπÑΓ ¡Ñ߬«½∞¬« ß«ßΓ«∩¡¿⌐ $S_{i_0,...,S_{i_k$ , Γᬿσ τΓ« Ññ¿¡ßΓóÑ¡¡δ¼ ñ«»πßΓ¿¼δ¼ »ÑαÑσ«ñ«¼ ñ½∩ $S_{i_j$ ∩ó½∩ÑΓß∩ »ÑαÑσ«ñ ¬ $S_{{i_j+1$ Γ.Ñ. ¬ ß½ÑñπεΘÑ¼π »« »«α∩ñ¬π ß«ßΓ«∩¡¿ε, Γ« ¼«ª¡« ñ«í¿Γ∞ß∩ ¡Ñ¬«Γ«α«⌐ «»Γ¿¼¿ºáµ¿¿ αáí«Γδ á½ú«α¿Γ¼á, αáßß¼áΓα¿óá∩ Γá¬¿Ñ ß¿Γπᵿ¿ «Γñѽ∞¡«, »«ß¬«½∞¬π ñ½∩ ¡¿σ óδτ¿ß½Ñ¡¿Ñ ß½ÑñπεΘÑú« º¡áτÑ¡¿∩ ¼á߬¿ $Cur$ ßó«ñ¿Γß∩ ¬ ÑÑ ßñó¿úπ ó½Ñó« ¡á 1 í¿Γ. Å«ßΓα«¿¼ í¿Γ«óπε ¼á߬π {\it NextReg »« ß½ÑñπεΘѼπ »αáó¿½π: $i-$⌐ í¿Γ αáóÑ¡ 1 Γ«úñá, ¬«úñá »ÑαÑσ«ñ «Γ $S_i$ 󫺼«ªÑ¡ Γ«½∞¬« ¬ $S_{i+1$.

\vskip 15 pt \vbox {\tt \+ \vCur = \vTableMask [0] ; \cr \+ \ppwhile & ( *$T$!=0 \&\& \vCur[$n$]==0 ) \cr \+& $\{$ \cr \+& \vCur \&= \vAsciiMask[*$T$++]; \cr \+& \ppif (&\vCur $\longrightarrow${\it NextReg) \cr \+&& \vCur<<=1; \cr \+& \ppelse $\{$ \cr \+&& \vTmp = \vTableMask [0] ; \cr \+&& \ppfor & ($i$=0 ; $i$ < $n$ ; $i$ ++) \cr \+&&& \ppif & ( \vCur [$i$] != 0) \cr \+&&&& \vTmp \char124= \vTableMask [$i$+1] ; \cr \+&& \vCur =$Tmp$ ; \cr \+&& $\$ \cr \+& $\$ \cr

çñÑß∞ »αÑñ¿¬áΓ {\it Cur$\longrightarrow$NextReg αáí«ΓáÑΓ ß½ÑñπεΘ¿¼ «íαẫ¼: ç¡áτÑ¡¿Ñ ”{\tt TRUE” ó«ºóαáΘáÑΓß∩ »α¿ óδ»«½¡Ñ¡¿¿ πß½«ó¿∩: Ñß½¿ $i-$⌐ í¿Γ {\it Cur αáóÑ¡ 1, Γ« $i-$⌐ í¿Γ {\it NextReg Γ«ªÑ αáóÑ¡ 1, ó »α«Γ¿ó¡«¼ ß½πτáÑ ó«ºóαáΘáÑΓß∩ º¡áτÑ¡¿Ñ ”{\tt FALSE”. ìÑΓαπñ¡« ºá¼ÑΓ¿Γ∞, τΓ« ñá¡¡δ⌐ »αÑñ¿¬áΓ ½Ñú¬« αÑ὿ºπÑΓß∩ »«ßαÑñßΓó«¼ ½«ú¿τÑ߬«⌐ Σπ¡¬µ¿¿ ¿¼»½¿¬áµ¿¿.

%&>>&13 0 A 12 %&<<&çá¼Ñτá¡¿Ñ »« »«ó«ñπ Γᬫ⌐ «»Γ¿¼¿ºáµ¿¿ ÄτÑó¿ñ¡«, τΓ« ó óδ᫪ñÑ¡¡«¼ ß½πτáÑ Γ.Ñ. Γ«úñá, ¬«úñá ñ½∩ ½εí«ú« $i$ »ÑαÑσ«ñ «Γ $S_i$ 󫺼«ªÑ¡ Γ«½∞¬« ¬ $S_{i+1$, ñá¡¡δ⌐ á½ú«α¿Γ¼ »αÑóαáΓ¿Γß∩ ó á½ú«α¿Γ¼, «»¿ßá¡¡δ⌐ ó ßΓáΓ∞Ñ [1].

\vskip 15 pt \vbox {\tt \+ \vCur = \vTableMask [0] ; \cr \+ \ppwhile & ( *$T$!=0 \&\& \vCur[$n$]==0 ) \cr \+& $\{$ \cr \+& \vCur \&= \vAsciiMask[*$T$++]; \cr \+& \vCur<<=1; \cr \+& $\$ \cr

é ß½πτáÑ ¬«α«Γ¬¿σ Φáí½«¡«ó, ¡á»α¿¼Ñα ¬«úñá ¿σ ñ½¿¡á ¡Ñ »αÑóδΦáÑΓ 16 ß¿¼ó«½«ó, ñá¡¡δ⌐ á½ú«α¿Γ¼ ¼«ª¡« ¼«ñ¿Σ¿µ¿α«óáΓ∞ ß ¿ß»«½∞º«ó᡿Ѽ ½«ú¿τÑ߬¿σ ¬«¼á¡ñ »α«µÑßß«αá. é Γᬫ¼ ß½πτáÑ ß¬«α«ßΓ∞ αáí«Γδ íπñÑΓ ºáó¿ßÑΓ∞ ½¿¡Ñ⌐¡« «Γ ñ½¿¡δ ΓѬßΓá, ó ¬«Γ«α«¼ »α«¿ºó«ñ¿Γß∩ »«¿ß¬. æ½ÑñπÑΓ ºá¼ÑΓ¿Γ∞, τΓ« »«ñ«í¡δÑ ¼«ñ¿Σ¿¬áµ¿¿ á½ú«α¿Γ¼á ¡Ñ ¿ß¬½ετáεΓ ¿ß»«½∞º«óá¡¿∩ ó Φáí½«¡Ñ «ñ¡«ß¿¼ó«½∞¡δσ WildCards.

%&>>&9 0 9 A

%&>>&5 0 5 B %&<<&References: \vskip 25 true pt

{\bf References:

\halign{ {\bf # \hfil & # \hfil \cr 1. & Sun Wu and Udi Mander {\it ”Fast Text Searching Allowing Errors” \cr & Communications Of The ACM / october 1992. \cr %&>>&0 0 0 F \end %&>>&1 0 1 E

This document was generated on February 15, 2023 using texi2html 5.0.