题解 P1032 【字串变换】

coyangjr · 2018-11-07 10:14:20 · 题解

萌新的第二篇题解。。

KMP解决本题

　　为啥要用find，为啥要用replace

　　其实是我考试时忘了 qwqwqwqwq

　　所以，我用的是KMP（AC自动机太难了）

整道题思路很简单

至多6个规则 和 若在10步(包含10步)以内

　　暗示了我们要去搜索。于是机房里的某dalao就开始了dfs。然后TLE，于是特判第五点（强烈谴责）

一般的，求解的个数用深搜，求最优解用广搜。

　　原因自己想 其实是广搜由于寻找顺序，导致找到一个解就一定是最优解了。

　　于是大框架是一个BFS，里面再去实现"取出队首元素，找字串，更改，放入队列" 这不摆明着是模式匹配吗

好的模版题传送门

P3375 【模板】KMP字符串匹配

P3808 【模板】AC自动机（简单版）

P3796 【模板】AC自动机（加强版）

　　由于本蒟蒻，AC自动机忘了。。于是写了KMP

　　具体的讲解上代码（不要走，后面更精彩）

//P1032 字串变换
#include <iostream>
#include <cctype>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <algorithm>
#include <sstream>
#include <queue>
#include <map>
#define debug cout << "debug"<<endl

using namespace std;
#define il inline
#define re register
typedef long long ll;

string a,b;

struct Node {//用于queue中存放，一个是字串，一个是搜索的“深度”
    string data;
    int step;
    Node(string _data,int _step):data(_data),step(_step) {}
    Node() {}
};
queue<Node>q;
string change[10];//改成哪个
string diff[10];//改哪个
/*即
搜索diff[i]
改成change[i]
*/

int nxt[10][10000];//kmp的next数组
map<string,bool>mp;//用于判重，避免重复搜索
il void get_next(int x)//找next，具体的可以翻翻网上的Blog。
{
    re int i,j=0;
    for (i=2; i<diff[x].length(); i++) {
        while (j&&diff[x][i]!=diff[x][j+1]) j=nxt[x][j];
        if (diff[x][j+1]==diff[x][i]) j++;
        nxt[x][i]=j;
    }
}

il void KMP(string a,int x,int step)//寻找匹配的串，顺便修改并添加到queue中
{
    string z=a;
    a=" "+a;//神奇的操作，。。。
    re int i,j=0;
    for (i=1; i<a.length(); i++) {
        while (j>0&&diff[x][j+1]!=a[i]) j=nxt[x][j];
        if (diff[x][j+1]==a[i]) j++;
        if (j==diff[x].length()-1) {//找到了~
            re int t= i-diff[x].length()+1;//记录位置
            string tmp=z.substr(0,t)+change[x]+z.substr(t+diff[x].length()-1);//修改（就不用replace，（真香））
            q.push(Node(tmp,step+1));
            j=nxt[x][j];//继续找
/*
第一次交由于脑子不好，找了一遍就return了。
*/
        }
    }
    return;
}

int cn=0;
int main()
{
    //freopen("in.txt","r",stdin);
    cin >> a >> b;
    string t1,t2;
    while (cin >>t1>>t2) {
        change[++cn]=t2;
        diff[cn]=" "+t1;//继续神奇的操作
        get_next(cn);
    }
    q.push(Node(a,0));
    while (!q.empty()) {
        Node now=q.front();
        q.pop();
        string x=now.data;
        if (mp[x]) continue;//map判重
        mp[x]=1;//标记
        if (now.step>10) {//找不到（因为bfs是按照step:1,2,3...来找的，所以一旦到了STEP11时一定无解了）
            puts("NO ANSWER!");
            exit(0);
        }
        if (x==b) {//找到，由于搜索有序，step一定是最小的
            cout << now.step<<endl;
            exit(0);
        }
        for (re int i=1; i<=cn; i++) {//枚举所有模式串，匹配文本串
            KMP(x,i,now.step);
        }
    }
    puts("NO ANSWER!");//最后由于map的判重，可能导致queue为空，于是到达这里的数据肯定是无解的
    exit(0);
}

有关KMP的Blog

　　KMP算法详解(Matrix67)以及字符串匹配的KMP算法(阮一峰)

都说了不要走了，String函数总结

　　string的函数，真香。(不总结迭代器的)

(由于NOIP2018，rp++，现在来总结一发string的函数)

• 最基本的，头文件

  #include <cstring>
  #include <string>

  就这两个含了string的，考试时一定要写

• 最最最基本的，大家都会的

  string a;//声明String a
  a="12345";//赋值
  string b="54321";
  int len=a.length();//获取长度
  cin >> a;//输入（以空格换行符为界限）
  getline(cin,a)//可以读入空格
  cout << a;
  swap(a,b)//交换
  printf("%s\n",a.c_str());//C风格输出，c_str()是啥？

• c_str()

返回一个char *， char类型的指针

关于char[ ],char *,string这些东西，尽量要用string全部用string，否则都用char[ ],后期两个转换自己认为很麻烦的。。

• 重载方面

+：连接两个String

string c=a+b;
c="123"+c+"321";

> < == != : 根据字典序比较

inline bool cmp(string a,string b)
{return a>b;}
...
int main()

    sort(a+1,a+1+n,cmp);

• insert() 插入

某个String a.insert(位置,另一个string)

    string str="to be question";
    string str2="the ";
    str.insert(6,str2);// to be (the )question

• erase() 删除

  erase(pos,n);

删除从pos开始的n个字符，比如erase(0,1)就是删除第一个字符

//接上
    str.erase(0,3); //(~~to ~~)be question

• clear() 清除

  清除。。。

• replace() 替换

某个String a.replace(pos,len,另一个String b)

替换a中pos开始往后len的这些字符为b

    str.replace(0,2,"To");// (To) be question

往往与find()一起使用。

• find()与rfind()

完全匹配String b

a.find(b) 从开始找b第一次出现的位置并返回

a.find(b,pos) 从pos开始找b第一次出现的位置并返回

string str="To be, or not to be - that is the question";
    int t=str.find("be");\\ t=3,str[t]='b'(To be 的be)
    int t=str.find("be",4);\\ t=17,str[t]='b'(not to be的be)

rfind(b)或rfind(b,pos) 倒着找O(∩_∩)O~

    int t=str.rfind("be");\\ t=17,str[t]='b'(not to be的be)
    int t=str.rfind("be",16);\\ t=3,str[t]='b'(To be 的be)

没有出现，返回npos，即-1（打印出来为4294967295）

if (str.find("Be")==string::npos)
    cout <<"NO"<<endl;// 输出NO
if (str.rfind("Be")==-1)
    cout <<"NO"<<endl; // 输出NO

• find_first_of()与find_last_of()

在a中寻找String b中任意一个字符 ‘(任意一个)’

a.find_first_of(b)或a.find_first_of(b,pos)

在a开始(或从pos开始)向后查找，只要在a中遇到一个字符，该字符与c中任意一个字符相同，就停止查找，返回该字符在a中的位置；若匹配失败，返回npos。

举个栗子

//将字符串中所有的元音字母换成*
//代码来自C++ Reference，地址：http://www.cplusplus.com/reference/string/basic_string/find_first_of/
#include<iostream>
#include<string>

using namespace std;

int main()
{
    std::string str("PLease, replace the vowels in this sentence by asterisks.");
    std::string::size_type found = str.find_first_of("aeiou");
    while (found != std::string::npos)
    {
        str[found] = '*';
        found = str.find_first_of("aeiou", found + 1);
    }
    std::cout << str << '\n';
    return 0;
}
//运行结果：
//PL**s* r*pl*c* th* v*w*ls *n th*s s*nt*nc* by *st*r*sks

find_last_of 倒着找

• find_first_not_of()与find_last_not_of()

感觉和前面一类的相反的，类似于找了个补集。即在a中搜寻b中没有的字符并返回位置

用法同上，第一个是String b,第二个可选 pos，不写pos默认为0

如果将上一个样例中的str.find_first_of改成str.find_first_not_of,则输出会把非a(あ)i(い)u(う)e(え)o(お)(逃。。。)的换成 *

总结一下“找”的函数的传参(string b,pos,len)

b是被搜寻的对象。pos（可有可无）指出a内的搜寻起点位置，第三个参数len（可有可无）指出b中搜寻的字符个数（即为b的某个字串）。

• substr() 字串

sub(start,length)

如果第二个参数不写，就是从start到字符串结尾。

string str="To be, or not to be - that is the question";
    str.substr(0,2);// To
    str.substr(str.find("question"));// question

• String与Int互转（不考虑C++11的函数）

  int转string

  ostringstream outs; //输出字符串流
  int x = 12; 
  outs << x; //向输出字符串流中输出x的内容 
  string a=outs.str(); //利用字符串流的str函数获取流中的内容

  string转int

  string a="12";
  istringstream ins(a); //输入字符串流，流的内容初始化为a
  int x; 
  ins >> x; //从is流中读入并存入x中

(没有用的东西。。)

• String与char的转换

  String转char*

  　　1.data()

  string str = "hello";
  const char* p = str.data();//加const  或者用char * p=(char*)str.data();的形式

  　　同时有一点需要说明，这里在devc++中编译需要添加const，否则会报错invalid conversion from const char to char ，这里可以再前面加上const或者在等号后面给强制转化成char*的类型。

　　下面解释下该问题，const char是不能直接赋值到char的,这样编译都不能通过,理由:假如可以的话,那么通过char就可以修改const char指向的内容了,这是不允许的。所以char要另外开辟新的空间，即上面的形式。

　　2. c_str()

string str=“world”;
const char *p = str.c_str();//同上，要加const或者等号右边用char*

　　3. copy()

string str="hmmm";
char p[50];
str.copy(p, 5, 0);//这里5代表复制几个字符，0代表复制的位置，
*(p+5)=‘\0’;//注意手动加结束符！！！

　　String转char[ ]，直接循环赋值

string pp = "dagah";
char p[8];
int i;
for( i=0;i<pp.length();i++)
    p[i] = pp[i];
p[i] = '\0';

总结部分 参考资料

c++中的string常用函数用法总结

C++string中用于查找的find系列函数浅析

C++中string、char *、char[]的转换

安利一波自己的Blog coyangjr