思路
这种类似的字符串匹配的问题,可以...
在s中记录每个字符的出现次数和对应次数的出现位置,然后用t去一一对应
首先,设lop[x][i] 储存 第i个x + 'a' 对应的字符在s中出现的位置,k代表t中我们要进行搜索的字符的位置
对于这道题,那就是记录完每个字符的出现位置之后,就枚举t串的每一个字符c,找出s中与c对应的第一个比c的位置大的位置,那么 ans += lop[c][j] - k
相反的,如果s中没有对应c比t中的c位置更大,也就是说,我们要再进行一个循环,这时, ans += lop[c][0] + n - k
自己画个图理解理解
代码
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <vector> using namespace std ; string s , t ; long long sum = 0 ; vector<int>c[30] ; int main () { cin >> s >> t ; int n = s.size() ; int m = t.size() ; for(int i = 0 ; i < s.size() ; i ++) { c[s[i]-'a'].push_back(i+1) ; } int x = t[0] - 'a' , j ; if(!c[x].size()) { puts("-1") ; return 0 ; } int k = c[x][0] ; sum += k ; for(int i = 1 ; i < m ; i ++) { x = t[i] - 'a' ; if(!c[x].size()) { puts("-1") ; return 0 ; } j = upper_bound(c[x].begin() ,c[x].end(),k) - c[x].begin() ; if(j == c[x].end()-c[x].begin() ) { sum += c[x][0] + n - k ; k = c[x][0] ; }else { sum += c[x][j] - k ; k = c[x][j] ; } } cout << sum <<endl ; return 0 ; }
京公网安备 11010502036488号