题解 P2395 【BBCode转换Markdown】

囧仙 · 2021-02-02 16:23:05 · 题解

题目大意

将一个 \text{BBCode} 的字符串转换成 \text{Markdown} 格式。具体格式参见下表：
\textbf{含义} &\textbf{BBC Code} & \textbf{Markdown} \cr\hline \text{一级标题} & \verb![h1]文字[/h1]! & \verb!# 文字 #! \cr\hline \text{二级标题} & \verb![h2]文字[/h2]! & \verb!# 文字 #! \cr\hline \text{斜体} & \verb![i]文字[i]! & \verb!*文字*! \cr\hline \text{粗体} & \verb![b]文字[b]! & \verb!__文字__! \cr\hline \text{链接} & \verb![url=地址]文字[/url]! & \verb![地址](文字)! \cr \text{图片} & \verb![img=地址]文字[/img]! & \texttt{!}\verb![地址](文字)! \cr\hline \text{代码块} & \verb![quote]文字[/quote]! & \begin{aligned}&\text{多行，每行前添加}\verb!"> "!\cr&\text{，有空格，不含引号}\end{aligned} \cr\hline \end{array}
若匹配错误，输出 \verb!Match Error! ；若未闭合，输出 \verb!Unclosed Mark! 。具体细节参见题面。

题解

题面描述不清啊……先提及几个可能出现的锅：

总输入量比较大，应该是介于 10^6 和 2\times 10^6 之间。如果你用数组存储，建议开到 2\times 10^6 。每个 \text{url} 的最大长度也不清楚……如果用数组，建议开大一些（比如 50,100 之类的）。
注意 \verb!quote! 。若 \verb![quote]! 不是另起一行的开头，那么需要换行；在 \verb![/quote]! 后无论是什么都要加上换行。
题面上说的什么“在输出 \text{Unclosed Mark} 的时候在 \text{close} 中间切开分为两段字符串”意义不明，直接输出 \verb!Unclosed Mark! 就行了。

下面开始正题。

对于标记匹配，我们可以用一个栈来维护。具体而言，遇到一个起始标签就入栈，遇到终止标签就弹出栈顶并比较，若不能匹配/栈空了则判定为匹配错误。如果最后还有东西在栈里，那么就判定为未闭合。
为了便于比较字符串，我们可以写一两个函数用于辅助我们的判断。比如比较一个字符串是否是另外一个的前缀、向一个字符串末尾增加一个字符串。这两者可在下方的代码中体现。
我们可以边读入，边将新的内容加入结果串。注意：我们并不能直接输出，因为在读完这个串前不能保证不会出现标记匹配错误的情况。
对于特殊的 \text{url,img} 标记，我们可以另外开一个栈用来存储 \verb!url=XXX,img=XXX! 的内容。在遇到终止标记时，我们可以取出这个特殊栈的栈顶并输出。当然，你也可以存储在输入串中的位置，这样可以节省一些空间。（尽管下面程序并没有这么做）。

其他倒也没什么，只要注意不出锅就行了。顺便附送一个主要是 \text{quote} 的样例数据。

不是很难的题，但是 \verb!quote! 卡人的确挺谔谔的……

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int MAXN=5e6+3,MAXM=5e4+3,MAXK=100+3;
char S[MAXN],T[MAXN],Q[MAXN],R[MAXN],M[MAXM][MAXK];
int s,n,t,r,m,o,O[MAXN];
bool cmp(char *A,const char *B){
    for(int p=0;B[p];++p) if(A[p]!=B[p]) return false; return true;
}
void ist(char *A,const char *B,int &l){for(int p=0;B[p];++p) A[l++]=B[p];}
void err(bool t){puts(t?"Match Error":"Unclosed Mark"),exit(0);}
void clc(){
    up(0,s-1,i) if(S[i]=='['){
        for(t=0;t<s&&S[i+t]!=']';++t) T[t]=S[i+t]; T[t++]=S[i+t];  int w=0;
        if(cmp(T,"[h1]")) w=1,ist(R,"# " ,r); else
        if(cmp(T,"[h2]")) w=2,ist(R,"## ",r); else
        if(cmp(T,"[i]" )) w=3,ist(R,"*"  ,r); else
        if(cmp(T,"[b]" )) w=4,ist(R,"__" ,r); else
        if(cmp(T,"[url")) w=5,ist(R,"["  ,r),memcpy(M[m++],T+5,t-6); else 
        if(cmp(T,"[img")) w=6,ist(R,"![" ,r),memcpy(M[m++],T+5,t-6); else 
        if(cmp(T,"[/h1]")) w=-1,ist(R," #" ,r); else
        if(cmp(T,"[/h2]")) w=-2,ist(R," ##",r); else
        if(cmp(T,"[/i]" )) w=-3,ist(R,"*"  ,r); else
        if(cmp(T,"[/b]" )) w=-4,ist(R,"__" ,r); else
        if(cmp(T,"[/url]")) w=-5,ist(R,"]",r); else 
        if(cmp(T,"[/img]")) w=-6,ist(R,"]",r); else 
        if(cmp(T,"[quote]")){
            for(t=0;t<s&&!cmp(S+i+t,"[/quote]");++t) T[t]=S[i+t];
            ist(T,"[/quote]",t); int a=7,b=t-9;
            while(T[a]=='\n') ++a; while(T[b]=='\n') --b;
            if(i>0&&S[i-1]!='\n') R[r++]='\n'; ist(R,"> ",r);
            up(a,b,j){
                if(j>a&&T[j-1]=='\n') ist(R,"> ",r); R[r++]=T[j];
            }
            R[r++]='\n';
        } else if(cmp(T,"[/quote]")) err(1);
        if(w>0) O[o++]=w; if(w<0){if(!o||O[o-1]!=-w) err(1); else --o;}
        if(w==-5||w==-6){
            --m,R[r++]='(',ist(R,M[m],r),R[r++]=')';
            memset(M[m],0,strlen(M[m]));
        }
        i+=t-1,memset(T,0,t);
    } else R[r++]=S[i];
    if(o) err(0);
}
int main(){
    s=fread(S,1,MAXN,stdin),clc(),fwrite(R,1,r,stdout);
    return 0;
}