字符串匹配与操作篇总结

0. 常见问题

1）从前往后容易会重复遍历，或者说重复移动，这时候可以考虑从后往前遍历，可能会减少遍历（移动）次数；

1. 字符串匹配算法

https://blog.nowcoder.net/n/c4edcbc44b3c43588876d6685b009409

2. 字符串重复问题

1）遍历。最容易想到的方法一般使用两层for循环遍历，时间复杂度为O(n*n)；
2）排序。对字符串排序，然后再判断是否有字符重复，需要O（nlogn)排序，然后再遍历一遍O(n)；⭐
3）Parition。基于快速排序的partition，可以边排序边找重复，也即是每次partition之后，判断中间key元素与两边元素是否相同，相同则返回false，不同再进行下一轮partition，快速排序的核心代码如下，时间复杂度也是O(nlongn)，但要比排序速度快；⭐⭐
2）哈希法。首先char类型判断重复，用hash数组最方便，借助于数组，只需要256个bool类型即可，O(n)的时间，但是需要额外的存储结构，也就是用空间换时间。⭐⭐⭐
PS：抽屉原理。若有256个字符，则257个字符中必然会出现重复的字符。

    bool quick_check(string &str,int low,int high){
        int first = low,last = high;
        char key = str[first];
        if (low>=high)
            return true;
        while(first<last){
            while(first <last && str[last] >= key)
                last--;           
            str[first] = str[last];
            while(first<last && str[first] <= key)
                first++;
            str[last] = str[first];
        }
        str[first] = key;
        if (first>low && str[first] == str[first-1])
            return false;
        if (first<high && str[first] == str[first+1])
            return false;
        return quick_check(str,low,first-1) && quick_check(str,first+1,high);
    }

3. 读取一行字符串

1）对于字符数组：
方法一：getline()
读入整行数据，它使用回车键输入的换行符来确定输入结尾。
调用方法: cin.getline(str, len);
第一个参数str是用来存储输入行的数组名称，第二个参数len是要读取的字符数。

方法二：get()
调用方法：cin.get(str, len);

两者都读取一行输入，直至换行符。
然后，getline将丢弃换行符，而get()将换行符保留在输入序列里。

2）对于string类
方法一:getline(cin, str)
这说明这里的getline不是类方法。
在这里要注意的是：当 getline(cin, str);前面的输入是cin>>ss;的话，那么此处str的值时空的，因为他会读取上一行的结束符。

参考文章：https://blog.csdn.net/qq_36770641/article/details/88552618

4. char[]，char *，string之间转换

1）char []转char *：直接进行赋值即可

char str[] = "lala";
char *str1 = str;

2）char *转char[]：字符拷贝实现，不能进行赋值操作

const char *st = "hehe";
char st1[] = "lalalala";
strncpy(st1, st, strlen(st) + 1); // 注意加1操作
// tp = temp; //错误，不能实现

3）char 与const char 之间转换

// const char 转char ：拷贝实现，不能进行赋值

// const char *转char *
const char *st = "lala";
// 直接赋值不可以
//char *st1 = st; // （不可以编译器报错）
// 另外开辟空间，将字符一个一个复制过去
char *ncstr = new char[strlen(st) + 1];
strcpy(ncstr, st);

// char 转const char ：直接进行赋值

// char *转const char *
char *st = "hehe"; // （编译提示警告）
const char *st1 = st;

4）char *与string之间转换

// char*转换为string
// （注意，定义char *变量，并直接赋值，最好定义为const变量，否则编译器警告）
const char *st = "hello";
// 赋值转换
string st1 = st;
cout << st1 << endl;
// 构造转换
string s1(st, st + strlen(st));
// 改变const char *变量值
st = "lalala";

// string转char *
string st = "My test";
//char *st1 = st; // 错误类型不同
//char *st1 = st.c_str(); // 错误类型不同
char *st1 = const_cast<char *>(st.c_str()) ;

5）char[]与string之间转换

// char[]转换为string
char st[] = "hello";
// 直接赋值实现
string st1 = st;
// 构造实现
string st2(st, st + strlen(st));
cout << st2 << endl;

// string转char []
string ts = "My test1";
//char ts1[] = ts; // 错误
//char ts1[] = const_cast<char *>(ts.c_str()); // 错误
char ts1[] = "lalallalalaaaa";
strncpy(ts1, ts.c_str(), ts.length() + 1); // 注意，一定要加1，否则没有赋值'\0'

总结：涉及到char []字符数组与其它类型转换，一般需要进行拷贝，不能直接赋值实现。char []和char *都可以通过构造新的string完成其对string的转换。涉及到到char *转换，需要注意类型一致，同时注意const的使用。