176B - Word Cut - CodeForces Solution

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map> 
#include<set>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

const int mod = 1e9 + 7;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	string st, ed;
	cin >> st >> ed;
	int fg = 0;
	if(st != ed) fg = 1;
	st = ' ' + st + st;
	ed = ' ' + ed;
	int k;
	cin >> k;
	vector<int> ne(ed.size());
	for(int i = 2, j = 0; i < ed.size(); i ++ ) {
	    while(j && ed[i] != ed[j + 1]) j = ne[j];
	    if(ed[i] == ed[j + 1]) j ++ ;
	    ne[i] = j;
	}
	int cnt = 0;
	for(int i = 1, j = 0; i < st.size() - 1; i ++ ) {
	    while(j && st[i] != ed[j + 1]) j = ne[j];
	    if(st[i] == ed[j + 1]) j ++ ;
	    if(j == ed.size() - 1) cnt ++ ;
	}
	vector<vector<int> > dp(k + 1, vector<int>(2, 0));
	dp[0][fg] = 1; // 0:代表ed  1:代表非ed的串
	for(int i = 1; i <= k; i ++ ) {
	    dp[i][0] = ((ll)dp[i - 1][0] * (cnt - 1) + (ll)dp[i - 1][1] * cnt) % mod;
	    dp[i][1] = ((ll)dp[i - 1][0] * (ed.size() - 1 - cnt) + (ll)dp[i - 1][1] * (ed.size() - 1 - cnt - 1)) % mod;
	}
	cout << dp[k][0];
	
	return 0;
}