网站建设排序题,建设网站用哪个主机好,如果修改wordpress后台登录域名,廊坊建站服务文章目录 7.字符串(1).字符串及其ADT#1.基本概念#2.ADT (2).字符串的基本操作#1.求子串substr#2.插入字符串insert#3.其他操作 (3).字符串的模式匹配#1.简单匹配(Brute-Force方法)#2.KMP算法I.kmp_match()II.getNext() #3.还有更多 小结附录#xff1a;我自己写的string 7.字符… 文章目录 7.字符串(1).字符串及其ADT#1.基本概念#2.ADT (2).字符串的基本操作#1.求子串substr#2.插入字符串insert#3.其他操作 (3).字符串的模式匹配#1.简单匹配(Brute-Force方法)#2.KMP算法I.kmp_match()II.getNext() #3.还有更多 小结附录我自己写的string 7.字符串 字符串几乎算得上是我们平时最常用的数据结构了比如你看到的这篇博客它也是由一系列的字符组成的。说实话字符串相关的问题其实多的非常离谱并且往后的各种问题也非常复杂。 我们可以举这么一个例子假设我给你一段C语言的代码
#include stdio.h
int main()
{int a 0;scanf(%d, a);printf(%d\n, a 10);return 0;
}这一段代码在你眼里看来是代码但是在gcc看来就是一串可能包含代码的字符串经过处理之后我们需要把这段代码解析成下面正确的汇编代码从而经过之后的链接器等完成最终可执行文件的生成操作而读入代码生成汇编文件这个过程就涉及到了有限自动机(FAM) 这个模型它将一个系统分成若干可数个离散的状态在识别到特定模式后进行对应的跳转最终再进行判断。 .file a.c.text.section .rodata.str1.1,aMS,progbits,1
.LC0:.string %d
.LC1:.string %d\n.text.globl main.type main, function
main:
.LFB11:.cfi_startprocsubq $24, %rsp.cfi_def_cfa_offset 32movl $0, 12(%rsp)leaq 12(%rsp), %rsimovl $.LC0, %edimovl $0, %eaxcall __isoc99_scanfmovl 12(%rsp), %eaxleal 10(%rax), %esimovl $.LC1, %edimovl $0, %eaxcall printfmovl $0, %eaxaddq $24, %rsp.cfi_def_cfa_offset 8ret.cfi_endproc
.LFE11:.size main, .-main.ident GCC: (GNU) 13.2.0.section .note.GNU-stack,,progbits而字符串的操作还远不止这些关于有限自动机以及编译器的实现细节等内容你将会在未来的编译原理课程中学到当然是你们学校开的课我还没有写编译原理博客的计划在这一篇当中我们会介绍字符串的ADT基本操作以及两种常用的字符串模式匹配算法。
(1).字符串及其ADT
#1.基本概念 假设V是程序语言所使用的字符集由字符集V中的字符所组成的任何有限序列称为字符串。 不包含任何字符的字符串称为空字符串而字符串的长度即为一个字符串所包含的字符个数某个串的子串则是这个串中任意一个连续的子序列。 所以字符串也是一种线性表其中的每个元素都是一个字符这样我们用数组和链表理论上讲都是可以实现字符串的不过通常情况下我们会采取顺序存储的方式来实现字符串因为有些算法可能涉及到随机访问所以用顺序存储会方便些
#2.ADT 具体的我就不提了这里就说一说关于字符串的一些操作
创建、赋值、拷贝、清空、销毁串互相比较求串的长度连接两个字符串取出字符串的子串判断是否为空串子串替换、插入、删除 接下来我们就来看看这些基本操作的实现方式。
(2).字符串的基本操作 这里的字符串的容器采取STL vector实现具体你可以试着自己写一写我在GitHub上开源了一个MySTL其中有基于vectorT的basic_stringT实现MySTL-Voltline
#1.求子串substr 求子串其实还挺简单的只是有一些边界情况需要考虑比如beg endbeg、end 0end _size这样所以就可以得到以下的代码
string substr(int beg, int end) const
{if (beg 0) beg 0;if (end _size) end _size;vectorchar vc;for (int i beg; i end; i) {vc.push_back(container[i]);}return string{ vc };
}还有一种子串的取法则是从位置i开始取j个字符形成子串这个实现方法其实没什么太大的区别你可以自己尝试实现。
#2.插入字符串insert 这个函数其实和线性表向其中某个位置插入指定个数的元素的操作差不多所以我们也可以很快地写出下面的代码
string insert(const string s1, int pos)
{if (pos _size) pos _size;else if (pos 0) pos 0;container.resize(_size s1.size() 100);// 给容器直接扩容避免之后再挪动的时候出现越界访问的问题int mov s1.size();for (int i _size-1; i pos; i--) {container[i mov] container[i]; }for (int i pos; i mov; i) {container[i] s1.container[i - pos];}return *this;
}#3.其他操作 其他操作真的很简单比如concat如果操作的是vector一个个push_back就好了这些操作还是自己实现一下吧。
(3).字符串的模式匹配 什么是模式匹配呢听起来有点复杂不过其实很简单就是依照查找子串的事情比如在hellowbabababbabbba中找到babb
#1.简单匹配(Brute-Force方法)
怎么找呢很自然的想法就是一个个去遍历比如这样
int find_bf(const string t, const string p, int pos)
{int i{ pos }, j{ 0 };int n t.size(), m p.size();while (i n j m) {if (t[i] p[i]) { i, j;}else {i 1-j;j 0;}}if (j m) return i - m;else return -1;
}很简单每到一个字符就往后匹配一次匹配不上就继续遍历如果匹配上了就直接返回这样就好了 假设正文字符串长度为n模式字符串长度为m那么这个匹配方式的时间复杂度是 O ( n m ) O(nm) O(nm)如果模式串和正文串长度差不多这个匹配方式的时间复杂度就会退化到 O ( n 2 ) O(n^2) O(n2)的时间复杂度这有点太慢了。
#2.KMP算法 KnuthMorris和Pratt共同提出了一种全新的模式匹配算法这个算法能够在 O ( n m ) O(nm) O(nm)的线性时间复杂度内完成字符串的模式匹配。 我们先来思考一下Brute-Force方法到底有什么问题比如t abababcbababbap ababcBF方法是这样 我们会发现p和t在第一次匹配的时候前面的abab都已经匹配上了只有c和a发生了失配而因为失配第二次我们把整个字符串往后挪动一次匹配还得从a开始这样我们貌似忘记了前面四个字符是匹配的了 如果我们试着看看t可能可以发现这么一件事出现的第二个ab后面又是a而在字符串p中第一个ab后出现的也是a所以如果我们的p可以这么跳转 只让p对应的那个指针动动到刚才我们发现的aba的地方就可以去掉第二次匹配这个例子举的可能差距不大我们把t变成abababababcbab那么情况就会变成这样 比较次数明显减少所以KMP算法的核心就在于如何找到模式字符串本身具备的特性通过它本身的性质得到一个失配跳转值从而尽可能增加每一次模式字符串跳转的字符数从而大大减少重复匹配的次数接下来我们来具体提一提怎么实现KMP算法
I.kmp_match() 这次我打算先介绍一下我们如何通过这个想法进行匹配假设我们已经获得了对于模式字符串的next数组这个等会儿再来看怎么实现接下来要对正文串t和模式串p进行匹配那么基于前面我们说的想法在匹配的时候就继续前进失配的时候根据失配跳转值让p向前跳如果到第一个字符还是失配那就不可能在现在已经走过的字符里找到能匹配的了这时候只要让t的指针往后跳一个就行了所以我们可以得出下面的代码
struct chars
{char c; // 字符int idx; // 跳转值
};int kmp(const string t, const string p)
{int ans{ -1 };vectorchars next getNext(p);int t_size t.size(), p_size p.size();int i{ 0 }, j{ 0 };while (i t_size) {if (j -1 || t[i] p[j]) {i, j;}else {if (j p_size) j next[j].idx;}if (j p_size) {ans i - j;break;}}return ans;
}我们首先用getNext()函数获得next数组然后进行基于next数组的匹配next数组的数据模式如下第一个字符对应的值为-1其他的字符对应的值则是对应字符失配时的跳转值如果找到的next值是-1就让指向正文串的指针i向后移动一位否则就让指向模式串的指针j移动到next[j]的位置上去。 那么接下来我们就来看看这个getNext()函数怎么写的吧
II.getNext() 首先说一说前缀和后缀的概念前缀就是自第一个字符起的所有连续子串后缀就是自最后一个字符起的所有连续子串提到前缀和后缀主要是为了引入next的计算原理。 接下来我们来看看next数组是怎么生成的next数组的跳转顺序基于这样一个规则当失配发生时失配字符a的上一个字符b对应的某一个子串S在不包含当前子串的最长前缀中子串S最后一次出现的位置中字符b的位置有点拗口我们来详细地解释一下例如p abcabd我们找next的规则就是基于每个下一个字符都有可能是失配字符来做的那么我们可以得到下面的一张表 a首先是-1没问题b去往前找只有a那就赋为0吧。之后是c往前找一个字符是b它对应的idx是0next[0]是aa和b并不匹配那就继续往前走字符a对应的idx是-1这时候就结束了我们让c的idx为a的idx1也就是0。 然后又是bb前面一个字符是a而a在前面的字符中出现过在第0个因此当这个b失配的时候下一次我们可以试着从它前面一个字符出现的上一次的后面一个字符继续匹配很显然a在0出现了后面一位是1所以b就赋为1了。 最后是dd前面一个字符是b而b上一次出现在数组中是1那么d失配的时候b满足就跳转到上一次出现的b的后面一位也就是c对应的是2所以d就赋为2了。 然后我们就走完了全程你发现了虽然我们是在做子串和前缀的重叠匹配但是实际上因为每个字符的上一个字符总是已经包含了之前字符的重叠情况因此我们只需要考虑当前这个字符是不是匹配就好了这其实也能算是一种动态规划的思想因为我们让每一次字符的查找都变得有用了起来每一次下一个字符的查找都基于上一个查找的结果来确定因此查找的过程就变得简单了起来
1.到了某一个字符c先看看这个字符的前一个字符2.如果这个字符的前一个字符b和b自己的next值对应的字符相同那就让c的next值等于b的next值1允许你从上一次b出现的后面一个字符开始匹配3.如果这个字符的前一个字符b和b自己的next值对应的字符不相同那就让继续找到b的next值对应的字符对应的next值继续往前找直到找到一个匹配的字符或者找到第一个字符对应的next值为-1如果找到匹配的字符则类似2操作让c的next值等于找到的这个字符的位置1否则就赋值为0对应最前的字符 很好那代码就很好写了
vectorchars getNext(const string sub_str)
{vectorchars next;size_t sub_str_size{ sub_str.size() };next.push_back(chars{ sub_str[0], -1 });for (size_t i 1; i sub_str_size; i) {next.push_back(chars{ sub_str[i], 0 });}for (size_t i 1; i sub_str_size; i) {if (next[i - 1].idx ! -1 next[i - 1].c next[next[i - 1].idx].c) {next[i].idx next[i - 1].idx 1;}else {int j next[i - 1].idx;while (j ! -1 next[j].c ! next[i - 1].c) {j next[j].idx;}next[i].idx j 1;}}return next;
}我这里next存的是一个叫做chars的结构体它对应的结构是这样
struct chars
{char c; // 字符int idx; // 跳转值
};其实你只存这个idx也是可以的你可以稍微改改有一个特别需要注意的点 for (size_t i 1; i sub_str_size; i) {next.push_back(chars{ sub_str[i], 0 });}这个数组在初始化的时候我们把所有后续字符的idx值都赋为0如果没有后续的操作这个情况如果调用kmp_match函数的匹配过程就会和前面说的Brute-Force方式完全一样了所以后续的找next过程还是非常重要的呢那么KMP算法其实到这里基本上就结束了我们会发现如果真的理解了它的做法其实感觉还挺简单的实际上就是一个动态规划的思想很多动态规划的问题也是这样其实想出来之后它的思路并不复杂但是要想到这个思路的过程是相当困难的。
#3.还有更多 其实字符串的匹配方式还有很多很多例如BM算法等因为时间的限制在这里我就不做过多介绍了。
小结 字符串这一篇相当的短啊哈哈哈哈哈哈毕竟这一部分在数据结构中我们主要还是以掌握KMP算法为主毕竟它在模式匹配上表现出的时间复杂度 O ( n m ) O(nm) O(nm)是非常优秀的。下一篇我们将会介绍一系列内部排序的算法。 然后我会在下面给出我写过的MySTL中的basic_string的代码仅供参考如果你发现了什么bug一定要告诉我哦这对我帮助很大
附录我自己写的string
#pragma once
#include iostream
#include cstring
#include vector.hnamespace MySTL
{template typename Tclass basic_string{private:vectorT container;size_t _size;public:using iterator T*;using const_iterator const T*;inline static size_t npos -1;public:basic_string();basic_string(const char* _c_str);basic_string(const char* _c_str, size_t _size);basic_string(const char* _c_str, size_t _begin, size_t _size);basic_string(size_t _size, char c);basic_string(const basic_stringT _str);basic_string(basic_stringT _mv_str) noexcept;basic_string(std::initializer_listT l);~basic_string();basic_stringT operator(const basic_stringT _Right);basic_stringT operator(basic_stringT _Right) noexcept;basic_stringT operator(const char* _str);basic_stringT operator(char c);basic_stringT operator(const basic_stringT _Right);basic_stringT operator(const char* _str);basic_stringT operator(char c);basic_stringT operator(const basic_stringT _Right);basic_stringT operator(const char* _str);basic_stringT operator(char c);T operator[](size_t _index);const T operator[](size_t _index) const;T at(size_t _index);bool operator(const basic_stringT _Right);bool operator!(const basic_stringT _Right);bool operator(const basic_stringT _Right);bool operator(const basic_stringT _Right);bool operator(const basic_stringT _Right);bool operator(const basic_stringT _Right);bool operator(const char* _c_Right);bool operator!(const char* _c_Right);bool operator(const char* _c_Right);bool operator(const char* _c_Right);bool operator(const char* _c_Right);bool operator(const char* _c_Right);size_t size() const noexcept;size_t capacity() const noexcept;bool empty() const noexcept;const T* data();const T* c_str();iterator begin();iterator end();const_iterator begin() const;const_iterator end() const;void reserve(size_t new_capacity_size);void resize(size_t new_elem_size);void clear();void erase(const size_t _Where);void erase(const size_t _Off, const size_t _Count);void erase(iterator _begin, iterator _end);void erase(iterator _pos);void append(size_t _Count, char c);void append(const basic_stringT _str);void append(const basic_stringT _str, size_t _Begin 0);void append(const basic_stringT _str, size_t _Begin, size_t _Count);void append(const char* _str);void append(const char* _str, size_t _Begin);void append(const char* _str, size_t _Begin, size_t _Count);void append(std::initializer_listchar l);void push_back(char c);size_t find(char c, size_t _begin_pos 0);size_t find(const char* _str, size_t _begin_pos 0);size_t find(const basic_stringT _str, size_t _begin_pos 0);void swap(basic_stringT _Right);templatetypename Ufriend std::ostream operator(std::ostream output, const basic_stringU _str){for (auto i : _str) {output i;}return output;}templatetypename Ufriend std::istream operator(std::istream input, basic_stringU _str){_str.clear();U c input.get();while (c ! c ! \n c ! \t) {_str.push_back(c);c input.get();}return input;}};templatetypename Tbasic_stringT::basic_string(){container vectorunsigned char{};}templatetypename Tbasic_stringT::basic_string(const char* _c_str){size_t length{ strlen(_c_str) };_size length;container vectorT();for (size_t i 0; i length; i) {container.push_back(*(_c_str i));}container.push_back(\0);}templatetypename Tbasic_stringT::basic_string(const char* _c_str, size_t _size){size_t length{ _size };if (_size strlen(_c_str)) {length strlen(_c_str);}_size length;container vectorT();for (size_t i 0; i length; i) {container.push_back(*(_c_str i));}container.push_back(\0);}templatetypename Tbasic_stringT::basic_string(const char* _c_str, size_t _begin, size_t _size){size_t c_str_len{ strlen(_c_str) };container vectorT();if (_begin c_str_len) {_size 0;}else {size_t length{ _size };if (_size strlen(_c_str _begin)) {length strlen(_c_str _begin);}_size length;for (size_t i _begin; i length; i) {container.push_back(*(_c_str i));}container.push_back(\0);}}templatetypename Tbasic_stringT::basic_string(size_t _size, char c){container vectorT(_size, c);_size _size;}templatetypename Tbasic_stringT::basic_string(const basic_stringT _str){container vectorT(_str.container);_size _str._size;}templatetypename Tbasic_stringT::basic_string(basic_stringT _mv_str) noexcept{container std::move(_mv_str.container);_size _mv_str._size;_mv_str.container vectorT{};}templatetypename Tbasic_stringT::basic_string(std::initializer_listT l){container vectorT(l.size() 128);_size l.size();for (auto it l.begin(); it ! l.end(); it) {container.push_back(static_castT(*it));}container.push_back(\0);}templatetypename Tbasic_stringT::~basic_string(){_size 0;container.~vector();}templatetypename Tbasic_stringT basic_stringT::operator(const basic_stringT _Right){container.~vector();container _Right.container;_size _Right._size;return *this;}templatetypename Tbasic_stringT basic_stringT::operator(basic_stringT _Right) noexcept{container.~vector();container std::move(_Right.container);_size _Right._size;return *this;}templatetypename Tbasic_stringT basic_stringT::operator(const char* _str){container.~vector();size_t length{ strlen(_str) };container vectorT(length 128);_size 0;for (size_t i 0; i length; i) {container.push_back(_str[i]);_size;}return *this;}templatetypename Tbasic_stringT basic_stringT::operator(char c){clear();push_back(c);return *this;}templatetypename Tbasic_stringT basic_stringT::operator(const basic_stringT _Right){basic_stringT temp{ *this };for (auto i : _Right) {temp.push_back(i);}return temp;}templatetypename Tbasic_stringT basic_stringT::operator(const char* _str){basic_stringT temp{ *this };size_t length{ strlen(_str) };for (size_t i 0; i length; i) {temp.push_back(_str[i]);}return temp;}templatetypename Tbasic_stringT basic_stringT::operator(char c){basic_stringT temp{ *this };temp.push_back(c);return temp;}templatetypename Tbasic_stringT basic_stringT::operator(const basic_stringT _Right){for (auto i : _Right) {push_back(i);}return *this;}templatetypename Tbasic_stringT basic_stringT::operator(const char* _str){size_t length{ strlen(_str) };for (size_t i 0; i length; i) {push_back(_str[i]);}return *this;}templatetypename Tbasic_stringT basic_stringT::operator(char c){push_back(c);return *this;}templatetypename TT basic_stringT::operator[](size_t _index){return container[_index];}templatetypename Tconst T basic_stringT::operator[](size_t _index) const{return container[_index];}templatetypename TT basic_stringT::at(size_t _index){if (_index _size) {return container[_index];}else {throw std::out_of_range(Index Out of Range);}}templatetypename Tbool basic_stringT::operator(const basic_stringT _Right){if (_size ! _Right._size) {return false;}else {for (size_t i 0; i _size; i) {if (container[i] ! _Right[i]) return false;}return true;}}templatetypename Tbool basic_stringT::operator!(const basic_stringT _Right){return !(*this _Right);}templatetypename Tbool basic_stringT::operator(const basic_stringT _Right){size_t min_size{ _size _Right.size() ? _size : _Right.size() };for (size_t i 0; i min_size; i) {if (container[i] _Right[i]) return true;else if (container[i] _Right[i]) {return false;}}return _size _Right.size();}templatetypename Tbool basic_stringT::operator(const basic_stringT _Right){return (*this _Right) (*this ! _Right);}templatetypename Tbool basic_stringT::operator(const basic_stringT _Right){return (*this _Right) || (*this _Right);}templatetypename Tbool basic_stringT::operator(const basic_stringT _Right){return !(*this _Right);}templatetypename Tbool basic_stringT::operator(const char* _c_Right){if (strlen(_c_Right) ! _size) return false;else {for (size_t i 0; i _size; i) {if (container[i] ! _c_Right[i])return false;}return true;}}templatetypename Tbool basic_stringT::operator!(const char* _c_Right){return !(*this _c_Right);}templatetypename Tbool basic_stringT::operator(const char* _c_Right){size_t length{ strlen(_c_Right) };size_t min_size{ _size length ? _size : length };for (size_t i 0; i min_size; i) {if (container[i] _c_Right[i]) return true;else if (container[i] _c_Right[i]) {return false;}}return _size length;}templatetypename Tbool basic_stringT::operator(const char* _c_Right){return (*this _c_Right) (*this ! _c_Right);}templatetypename Tbool basic_stringT::operator(const char* _c_Right){return (*this _c_Right) || (*this _c_Right);}templatetypename Tbool basic_stringT::operator(const char* _c_Right){return !(*this _c_Right);}templatetypename Tsize_t basic_stringT::size() const noexcept{return _size;}templatetypename Tsize_t basic_stringT::capacity() const noexcept{return container.capacity();}templatetypename Tbool basic_stringT::empty() const noexcept{if (_size ! 0) return false;else return true;}templatetypename Tconst T* basic_stringT::data(){return container.data();}templatetypename Tconst T* basic_stringT::c_str(){return container.data();}templatetypename Ttypename basic_stringT::iterator basic_stringT::begin(){return container.begin();}templatetypename Ttypename basic_stringT::iterator basic_stringT::end(){return container.begin() _size;}templatetypename Ttypename basic_stringT::const_iterator basic_stringT::begin() const{return container.begin();}templatetypename Ttypename basic_stringT::const_iterator basic_stringT::end() const{return container.begin() _size;}templatetypename Tvoid basic_stringT::reserve(size_t new_capacity_size){container.reserve(new_capacity_size);}templatetypename Tvoid basic_stringT::resize(size_t new_elem_size){container.resize(new_elem_size);_size new_elem_size;}templatetypename Tvoid basic_stringT::clear(){_size 0;container.clear();}templatetypename Tvoid basic_stringT::erase(const size_t _Where){if (_Where _size) {_size _Where;container.erase(container.begin() _Where, container.end());container.push_back(\0);}}templatetypename Tvoid basic_stringT::erase(const size_t _Off, const size_t _Count){if (_Off _size) {if (_size - _Off _Count) {_size - _Count;container.erase(container.begin() _Off, container.begin() _Off _Count);container[_size] \0;}else {erase(_Off);}}}templatetypename Tvoid basic_stringT::erase(basic_stringT::iterator _begin, basic_stringT::iterator _end){if (_end _begin) {if (_begin begin()) {size_t _Off _begin - begin();size_t _Count _end - _begin;if (_Off _size) {if (_size - _Off _Count) {_size - _Count;container.erase(container.begin() _Off, container.begin() _Off _Count);container[_size] \0;}else {erase(_Off);}}}else {throw IteratorOutOfRangeException{};}}else {throw IteratorErrorException{};}}templatetypename Tvoid basic_stringT::erase(basic_stringT::iterator _pos){if (_pos begin()) {if (_pos end()) {size_t _Where _pos - begin();if (_Where _size) {_size--;container.erase(_pos, _pos 1);container[_size] \0;}}}else {throw IteratorErrorException{};}}templatetypename Tvoid basic_stringT::append(size_t _Count, char c){for (size_t i 0; i _Count; i) {push_back(c);}}templatetypename Tvoid basic_stringT::append(const basic_stringT _str){*this _str;}templatetypename Tvoid basic_stringT::append(const basic_stringT _str, size_t _Begin){if (_Begin _str.size()) {if (_Begin 0) {*this _str;}else {for (auto it _str.begin() _Begin; it ! _str.end(); it) {push_back(*it);}}}else {throw std::out_of_range(Begin index out of range!);}}templatetypename Tvoid basic_stringT::append(const basic_stringT _str, size_t _Begin, size_t _Count){if (_Begin _str.size()) {if (_Begin _Count _str.size()) {_Count _str.size() - _Begin;}for (size_t i 0; i _Count; i) {push_back(_str[_Begin i]);}}else {throw std::out_of_range(Begin index out of range!);}}templatetypename Tvoid basic_stringT::append(const char* _str){*this _str;}templatetypename Tvoid basic_stringT::append(const char* _str, size_t _Begin){if (_Begin strlen(_str)) {*this (_str _Begin);}else {throw std::out_of_range(Begin index out of range!);}}templatetypename Tvoid basic_stringT::append(const char* _str, size_t _Begin, size_t _Count){if (_Begin strlen(_str)) {if (strlen(_str) - _Begin _Count) {_Count strlen(_str) - _Begin;}if (_Count ! 0) {for (size_t i 0; i _Count; i) {push_back(_str[_Begin i]);}}}else {throw std::out_of_range(Begin index out of range!);}}templatetypename Tvoid basic_stringT::append(std::initializer_listchar l){for (auto i : l) {push_back(i);}}templatetypename Tvoid basic_stringT::push_back(char c){if (_size container.size()) {container.push_back(c);}else {container[_size] c;}container.push_back(\0);_size;}templatetypename Tsize_t basic_stringT::find(char c, size_t _begin_pos){for (size_t i _begin_pos; i _size; i) {if (container[i] c) {return i;}}return npos;}templatetypename Tsize_t basic_stringT::find(const char* _str, size_t _begin_pos){size_t length{ strlen(_str) };bool isFind{ true };if (_size length) return npos;else {for (size_t i _begin_pos; i _size; i) {if (_size - i length) {if (container[i] _str[0]) {isFind true;for (size_t j 1; j length; j) {if (container[i j] ! _str[j]) {i i j - 1;isFind false;break;}}if (isFind) return i;}}else {return npos;}}return npos;}}templatetypename Tsize_t basic_stringT::find(const basic_stringT _str, size_t _begin_pos){size_t length{ _str.size() };bool isFind{ true };if (_size length) return npos;else {for (size_t i _begin_pos; i _size; i) {if (_size - i length) {if (container[i] _str[0]) {isFind true;for (size_t j 1; j length; j) {if (container[i j] ! _str[j]) {i i j - 1;isFind false;break;}}if (isFind) return i;}}else {return npos;}}return npos;}}templatetypename Tvoid basic_stringT::swap(basic_stringT _Right){basic_stringT temp{ _Right };_Right.clear();for (auto c : *this) {_Right.push_back(c);}clear();for (auto c : temp) {push_back(c);}}templatetypename Tbool operator(const char* _Left, const basic_stringT _Right){return _Right _Left;}templatetypename Tbool operator!(const char* _Left, const basic_stringT _Right){return _Right ! _Left;}templatetypename Tbool operator(const char* _Left, const basic_stringT _Right){return _Right _Left;}templatetypename Tbool operator(const char* _Left, const basic_stringT _Right){return _Right _Left;}templatetypename Tbool operator(const char* _Left, const basic_stringT _Right){return _Right _Left;}templatetypename Tbool operator(const char* _Left, const basic_stringT _Right){return _Right _Left;}templatetypename Tstd::istream getline(std::istream input, basic_stringT _Target, const char _End \n){_Target.clear();T c input.get();while (c ! \n) {_Target.push_back(c);c input.get();}return input;}using string basic_stringchar;using wstring basic_stringwchar_t;
#ifdef __cpp_lib_char8_tusing u8string basic_stringchar8_t;
#endif // __cpp_lib_char8_tusing u16string basic_stringchar16_t;using u32string basic_stringchar32_t;
}
