I need help, I got WA on test case 5, and I do not know what's the problem.
Here my code:
#include <bits/stdc++.h>
using namespace std;
string getPrefix(string s, int n){
    string result;
    if(n >= s.size())result = s;
    else result = s.substr(0,n);
    return result;
}
string getSuffix(string s, int n){
    int newN;
    string result;
    if(n >= s.size()) result = s;
    else result = s.substr(s.size() - n);
    return result;
}
int main(){
    string s, a, b;
    int m;
    while(cin>>s>>a>>b>>m){
        vector<pair<string, string> > v(m + 10, {"",""});
        vector<long long int> cnt(m + 10, 0);
        v[1] = {a, a}; cnt[1] = 0;
        v[2] = {b, b}; cnt[2] = 0;

        long long int maxi = 0;
        for(int i = 3, from, to; i <= m + 2;i++){
            cin>>from>>to;
            string text = v[from].second + v[to].first;
            string text2 = v[from].first + v[to].second;

            string prefix = getPrefix(text, s.size() - 1);
            string suffix = getSuffix(text, s.size() - 1);

            string prefixNew = getPrefix(text2, s.size() - 1);
            string suffixNew = getSuffix(text2, s.size() - 1);

            v[i] = {prefixNew, suffixNew};

            cnt[i] = (cnt[from] + cnt[to]) % 1000000007;
            if(text.size() >= s.size()){
                for(int j = 0 ; j < text.size() - s.size() + 1; j++){
                    if(s == text.substr(j,s.size()) ) cnt[i] = (cnt[i] + 1) % 1000000007;
                }
            }
        }
        long long int sol = 0;
        for(int i = 1; i <= m + 2; i++){
            sol = max(sol, cnt[i]);
        }
        cout<<sol<<endl;
    }
    return 0;
}