#include<bits/stdc++.h> using namespace std; void getNext(vector<int>& next, string str) { next[0] = 0; int i, j = 0; for (i = 1; i < next.size(); i++) { while (j > 0 && str[j] != str[i]) { j = next[j - 1]; } if (str[j] == str[i]) { j++; } next[i] = j...