Group: algorithms
Topic: approximate string matching and pattern matching with errors
Topic: boolean values, binary numbers, and bit strings
Topic: pattern matching
Topic: processing a sequence
Topic: search algorithms
Topic: sort algorithms
Topic: strings
Topic: string and list concatenation
Topic: string transformation languages
Topic: subsequences
 
Summary
Many operations have been defined for strings including: compare, concatenate, count, delete components, delimitate tokens, deque from end, edit, enque, head, insert, limit length, membership, merge, ordered insertion, permute, predecessor, repeat, replace, restructure, rotate left or right, shift left or right, sort, substring, successor, tail, test for null. Most operations use finite length strings. A number of languages exist primarily for string operations. (cbb 5/80)
Subtopic: external memory operation
Quote: survey of external memory algorithms; includes sorting, permuting, FFT, graphs, databases, GIS, text processing [»vittJS6_2001]
 Subtopic: shortest edit distance
Quote: algorithms for the shortest edit sequence for converting between two strings [»tichWF11_1984]
 Quote: algorithm for stringtostring correction problem using edit operations; time proportional to the product of the string lengths [»wagnRA1_1974]
 Subtopic: longest common subsequence, LCS
Quote: a fast and practical bitvector algorithm for length of longest common subsequence [»crocM12_2001]
 Quote: given length of longest common subsequence (LCS), generate the subsequence using Hirchberg's paradigm [»crocM12_2001]
 Quote: file differences as a minimal list of line changes; longest common subsequence; linear complexity in practice [»huntJW7_1976]
 Subtopic: maximal repeating pattern, covering set
Quote: a maximal repeating pattern is as long as possible or occurs independently; use position trees for quadratic algorithm [»siocAC10_1991]
 Quote: algorithm for minimal covering set of common substrings
 Subtopic: concate, repeat, extract
QuoteRef: schwJT_1973 ;;501 string operations concatenation (+), repetition (*), size (#), extraction (a(1:h) )
 Subtopic: string rewrite
QuoteRef: grayJC_1973 ;;169 merge (A '++ B) the blank indices (may be set blank) of A are replaced by corresponding values in B
 QuoteRef: grayJC_1973 ;;169 restructure (<%) result := newidemformat <% item by common index names.
 QuoteRef: mullAP_1964 ;;452 definition by n A n(3)(3)H(1)B(2)C(1)D(3) then can "insert the value string into another, or "join" two named strings together(retain names)
 QuoteRef: mullAP_1964 ;;452 have set operations on strings, induce structure, edit, count levels, e.g., A count ".circle2." > B where A is n A n.circle4..circle4.A.circle1.C.circle2.C.circle1.D.circle3 generates n B n.circle1.2.circle2
 Subtopic: bitvector
Quote: unidirectional bitvector analysis used for liveness, reaching def, defuse, code motion, partial dead code, and strength reduction; works for parallel programs [»knooJ5_1995]
 Subtopic: split and join
QuoteRef: sammJE_1969 ;;427 expand and compression functions on constitutes e.g. The+dog becomes under * $1+$1=//*e1 2* T+h+e+d+o+g and reversed by *$3+$=//*k1,*k2*
 Subtopic: cursor operation
Quote: in Icon, use 'move' and 'tab' to move cursor and return the intervening substring [»grisRE4_1980, OK]
 Subtopic: permute
QuoteRef: grayJC_1973 ;;169 permute (indexset '% set) e.g., [3 2]'%[a b c d] == [c b]
 Subtopic: justification
QuoteRef: seedH_1971 ;;160 string moves both left and right justified
 Subtopic: examples
QuoteRef: ledgHF9_1971 ;;136 PANON AXLE: string manipulation
 Subtopic: cost of string operations
Quote: OS6 profile showed almost all execution time spent in unpacking buffers, testing contents, and storing elsewhere [»stoyJE3_1972]

Related Topics
Group: algorithms (6 topics, 94 quotes)
Topic: approximate string matching and pattern matching with errors (19 items)
Topic: boolean values, binary numbers, and bit strings (44 items)
Topic: pattern matching (42 items)
Topic: processing a sequence (17 items)
Topic: search algorithms (40 items)
Topic: sort algorithms (24 items)
Topic: strings (13 items)
Topic: string and list concatenation (9 items)
Topic: string transformation languages (17 items)
Topic: subsequences (13 items)
