#include #include #include #include #include #include #include #include #include // require sort next_permutation count __gcd reverse etc. #include // require abs exit atof atoi #include // require scanf printf #include #include // require accumulate #include // require fabs #include #include #include #include // require setw #include // require stringstream #include // require memset #include // require tolower, toupper #include // require freopen #include // require srand #define rep(i,n) for(int i=0;i<(n);i++) #define ALL(A) A.begin(), A.end() using namespace std; typedef long long ll; typedef pair P; const int MAX_V = 50; int par[MAX_V]; // 親 // n 要素で初期化 void uf_init (int n ){ rep (i, n ){ par[i] = i; } // end rep } // 木の根を求める int uf_find (int x ){ if (par[x] == x ) return x; else return par[x] = uf_find (par[x] ); } // x と y の属する集合を併合 void uf_unite (int x, int y ){ x = uf_find (x ); y = uf_find (y ); if (x == y ){ return; }else if (x < y ){ par[y] = x; }else{ // if x > y par[x] = y; } // end if } bool uf_same (int x, int y ){ return uf_find (x) == uf_find (y ); } int uf_size(void ){ set res; res.clear(); rep (i, MAX_V ){ res.insert (uf_find(par[i] ) ); } // end rep set::iterator it = res.begin(); return res.size(); } const string weekly = "xxxxxxx"; int cnt[50]; int max_holiday (string s ){ memset (cnt, 0, sizeof (cnt ) ); cnt[0] = (s[0] == 'o' ); int n = s.length(); for (int i = 1; i < n; i++ ){ if (s[i] == 'o' ) cnt[i] = cnt[i-1] + 1; else cnt[i] = 0; } // end for int res = 0; rep (i, n ) res = max (res, cnt[i] ); return res; } /* OK! xxxxooooxxxx --oooooo---- NG! xxxxooooxxxx ---oooooo--- OK! ooooxxxxoooo ---oooooo--- NG! xxxxooooxoxx ---ooooooo-- ×が連続している部分は OK。 ×が離れて存在する部分は NG。 */ bool is_concated (string s ){ int n = s.length(); if (n == 1 ) return true; uf_init (n ); for (int i = 1; i < n; i++ ){ if (s[i-1] == 'x' && s[i-1] == s[i] ) uf_unite (i-1, i ); } // end for int res = uf_size(); // cerr << res << endl; return (res == 1 ); } string replace (string s, string t, int p ){ string u = ""; if (!is_concated (s.substr(p, t.length() ) ) ) return u; u = s; rep (i, t.length() ) u[p+i] = t[i]; return u; } int main() { ios_base::sync_with_stdio(0); int D; cin >> D; string c1; cin >> c1; string c2; cin >> c2; string s = ""; rep (i, 2 ) s += weekly; s += c1; s += c2; rep (i, 2 ) s += weekly; string t = ""; rep (i, D ) t += 'o'; int res = 0; rep (i, s.length() - t.length() + 1 ){ string u = replace (s, t, i ); bool ok = (!u.empty() ); int curr = 0; if (ok ){ // cerr << u << endl; curr = max_holiday (u ); } // end if res = max (res, curr ); } // end rep cout << res << endl; return 0; }