牛客多校第九场 Niuniu is practicing typing.（kmp优化）

本文主要是介绍牛客多校第九场 Niuniu is practicing typing.（kmp优化），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：https://www.nowcoder.com/acm/contest/147/F
来源：牛客网
 

Niuniu is practicing typing.

Given n words, Niuniu want to input one of these. He wants to input (at the end) as few characters (without backspace) as possible,

to make at least one of the n words appears (as a suffix) in the text.

Given an operation sequence, Niuniu want to know the answer after every operation.

An operation might input a character or delete the last character.

输入描述:

The first line contains one integer n.
In the following n lines, each line contains a word.
The last line contains the operation sequence.
'-' means backspace, and will delete the last character he typed.He may backspace when there is no characters left, and nothing will happen.1 <= n <= 4
The total length of n words <= 100000The length of the operation sequence <= 100000The words and the sequence only contains lower case letter.

输出描述:

You should output L +1 integers, where L is the length of the operation sequence.The i-th(index from 0) is the minimum characters to achieve the goal, after the first i operations.

示例1

输入

复制

2
a
bab
baa-

输出

复制

1
1
0
0
0

这个题就可以先考虑只有一个模式串，在一个模式串下我们和操作串进行匹配，如果在模式串的i位置失配，那么跳到模式串的Next[i] 的位置，如果没有删除操作，那么就是一个kmp的复杂度，可是现在可以删除，理论上加一个栈记录与模式串匹配的位置，可以实现回退。可是会有这样一个问题。

模式串 ：aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

操作传     aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab-c-v-d-s-d-a-w-........

这样以来，失配以后每次都要大量的跳转，非常费时间。因此考虑记录每个位置失配以后，每个字母对应的应该跳到的位置，

这样一来，每一次跳转肯定都是0（1）啦。

因为所给的要匹配的字符串长度随时变化，可以用变量cur记录字符串里有几个字符，pos[cur] 记录第cur个字符在模式串的匹配位置。那么如果是删除操作，只需要cur -- ，字符减少一个。如果是加字符，只需要cur++，pos[cur] 纪录新加字母后模式串匹配的位置。

#include <bits/stdc++.h>
using namespace std;const int maxn = 1e5+666;int n,Next[maxn],pre[maxn][26],Min[maxn],pos[maxn];
char s[5][maxn],sx[maxn];void getNext(char s[])
{int len = strlen(s),i = 0;int k = -1;Next[0] = -1;while(i < len){if(k == -1 || s[k] == s[i]){Next[++i] = ++k;}else{k = Next[k];}}for(int i = 0; i <= len; i++){for(int j = 0; j < 26; j++)pre[i][j] = i == 0 ? 0 : pre[Next[i]][j];if(i < len) pre[i][s[i]-'a'] = i+1;}
}void solve(char s[])
{getNext(s);int cur = 0;pos[0] = 0;int len = strlen(s);Min[0] = min(Min[0],len);for(int i = 1; sx[i]; i++){if(sx[i] == '-'){cur = max(cur-1,0);}else{pos[cur] = pre[pos[cur++]][sx[i]-'a'];	}Min[i] = min(Min[i],len-pos[cur]);}
}int main()
{scanf("%d",&n);for(int i = 1; i <= n; i++) scanf("%s",s[i]);scanf("%s",sx+1);int len = strlen(sx+1)+1;memset(Min,63,sizeof(Min));for(int i = 1; i <= n; i++) solve(s[i]);for(int i = 0; i < len; i++){printf("%d\n",Min[i]);}return 0;
}

 

这篇关于牛客多校第九场 Niuniu is practicing typing.（kmp优化）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---