1423
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <math.h> #include <limits.h> using namespace std; // Datatypes typedef vector<int> vi; typedef vector<string> vs; typedef vector<vi> vvi; typedef pair<int,int> ii; typedef long long ll; typedef long double ld; // Define #define sz(a) int((a).size()) #define pb push_back #define all(c) (c).begin(),(c).end() #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define FOR(_i,_n) for(int (_i) = 0; (_i) < (_n); (_i)++) #define mp make_pair // Constants const double eps = 1e-8; const double PI = 3.1415926535897932384626433832795; #define INPUT_FILE "xo.in" #define OUTPUT_FILE "xo.out" #define N 2*250000 #define M 250000 char s[N+10]; char p[M+10]; int l[M+10]; int n; int m; int jump(int x, char c) { while(1) { if(p[x] == c) return (x+1); if(x == 0) return 0; x = l[x]; } } void build() { l[0] = l[1] = 0; for(int i = 2; i <= m; i++) l[i] = jump(l[i-1], p[i-1]); } int search() { int q = 0; for(int i = 1; i < n; i++) { q = jump(q, s[i]); if(q == m) { /* found */ return (i-m+1); } } return -1; } int main(void) { #ifdef ALEX freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #else //freopen(INPUT_FILE, "r", stdin); //freopen(OUTPUT_FILE, "w", stdout); #endif cin >> n; cin >> s; cin >> p; copy(s, s+n, s+n); m = n; n = 2*n; build(); int offset; offset = search(); if(offset == -1) cout << -1; else if(offset == 0) cout << 0; else cout << m-offset; return 0; }
page revision: 0, last edited: 01 May 2007 10:44