在计算机科学中，"串(String)"是一种基本且重要的数据结构类型。它是由零个或多个字符（包括字母、数字或其他符号）组成的有限序列，在实际应用如文本处理、搜索引擎算法以及编程语言实现等领域扮演着核心角色。
一、基础概念
1. **定长与变长字符串**：从存储方式上看，串可以分为两种主要形式——定长和变长。定长串的长度固定，无论内容是否填满都占用同样大小的空间；而变长串则按需分配内存空间以适应其内部字符数量的变化，这样能更有效地利用系统资源。
2. **空串与非空串**：若一个串不含任何字符，则称为空串或者null string，用""表示。反之包含至少一个字符的就是非空串。
3. **子串(Substring)**：对于任意两个整数i和j(0≤ i ≤ j)，串中的第i到第j-1号位置上的所有连续字符组成的一个新串称为原串的子串。
4. **模式匹配(Pattern Matching)**：在主串S中查找是否存在某个给定的子串P的过程即为模式匹配问题，这是对串操作的一种重要需求，广泛应用于搜索引擎的关键字检索等场景。
二、串的相关定义及性质：
1. **串的基本运算**：
- 字符访问：获取指定索引处的单个字符。
- 长度计算：返回串内所含字符的数量。
- 连接(concatenation)：将两个或更多的串连接成一个新的串。
- 插入/删除字符：向串特定位置插入或移除字符的操作。
- 子串提取：取出满足条件的部分形成新的串。
2. **相等性判断(Equivalence Testing)**：通过比较两串的所有对应元素来确定它们是否完全相同。
3. **KMP算法等相关理论技术**：针对高效解决“在一个大串里找一个小串”的问题提出了诸如Knuth-Morris-Pratt(KMP)这样的动态规划预处理方法，极大地提高了大规模字符串比对效率。
三、抽象数据类型的表示与实现：
- 线性数组：一种常见的物理实现是使用线性顺序表进行存放，每个单元格存放下一个字符，并附带记录串的实际长度的信息以便于管理和执行各种操作。
- 双链表：另一种可行的方式则是采用双向循环列表的形式，这种方式便于灵活地进行前后端插入和删除操作。
- 堆栈与队列：当需要按照某种规则遍历并分析字符串时，例如回溯法解析表达式树或深度优先搜索解决问题时，堆栈和队列也是常用的数据组织工具。
总结来说，“串”这一数据结构承载了丰富的逻辑意义和技术内涵，无论是底层硬件设计还是上层软件开发都有广泛应用。深入理解和熟练掌握串的各种属性及其相应操作原理，无疑是提升程序员专业素养的重要环节之一。
