題目鏈接：點(diǎn)擊打開鏈接

#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<vector> using namespace std; typedef long long ll; const int mod = 1000000000 + 7; const int N = 100+10; struct node {char s1[N], s2[N];int len1, len2, g; };char s[N]; int len, f[N]; node a[N];void init(node& x) {scanf("%s", x.s1);x.len1 = x.len2 = strlen(x.s1);for (int i = 0; i < x.len1; ++i)x.s2[i] = x.s1[x.len1 - i - 1];x.g = 0;int j = 0;for (int i = 0; i < x.len1; ++i) {while (j && x.s1[i] != s[j])j = f[j];if (x.s1[i] == s[j])++ j;if (j == len) {++ x.g;j = f[j];}}if (x.len1 >= len - 1)x.len1 = x.len2 = len - 1; } void make() {int j;f[0] = f[1] = 0;for (int i = 1; i < len; ++i) {j = f[i];while (j && s[j] != s[i])j = f[j];if (s[j] == s[i])f[i + 1] = j + 1;elsef[i + 1] = 0;} } node get(node& x, node& y) {node re;re.g = (x.g + y.g) % mod;int j = 0;for (int i = x.len2 - 1; i >= 0; --i) {while (j && x.s2[i] != s[j])j = f[j];if (x.s2[i] == s[j])++ j;}for (int i = 0; i < y.len1; ++i) {while (j && y.s1[i] != s[j])j = f[j];if (y.s1[i] == s[j])++ j;if (j == len) {re.g = (re.g + 1) % mod;j = f[j];}}re.len1 = x.len1;for (int i = 0; i < x.len1; ++i)re.s1[i] = x.s1[i];if (re.len1 < len - 1) {for (int i = 0; i < y.len1; ++i) {re.s1[re.len1++] = y.s1[i];if (re.len1 == len - 1)break;}}//re.len2 = y.len2;for (int i = 0; i < y.len2; ++i)re.s2[i] = y.s2[i];if (re.len2 < len - 1) {for (int i = 0; i < x.len2; ++i) {re.s2[re.len2++] = x.s2[i];if (re.len2 == len - 1)break;}}return re; } int main() {int m, u, v, n;while (~scanf("%s", s)) {len = strlen(s);make();init(a[1]);init(a[2]);n = 2;scanf("%d", &m);while (m -- >0) {scanf("%d%d", &u, &v);a[++n] = get(a[u], a[v]);}printf("%d\n", a[n].g);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的URAL 1646 Godzilla Strikes Back!的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。