Dəli alim (Həll təhlili)

$a$ və $b$ sətirlərinə soldan sağa baxacağıq. Sətirlərin simvollarının fərqləndiyi mövqeləri nəzərdən keçirək. Tutaq ki, $i$ — a_i \ne b_i şərtinin ödəndiyi ilk belə mövqenin indeksidir. Bu o deməkdir ki, $b$ sətrinin $i$ mövqeyindəki simvolu tərsinə çevrilməlidir. Bu anda biz maşının tətbiq ediləcəyi intervalın başlanğıcını sabitləyirik.

Sonra, sətirlərin simvolları fərqlənməyə davam etdiyi müddətcə sağa doğru hərəkət etməyə davam edirik, yəni i \le k \le j intervalındakı bütün $k$ indeksləri üçün a_k \ne b_k şərti ödənilir. a_{j+1} = b_{j+1} şərtinin ödəndiyi j + 1 mövqeyinə rast gəlindiyi an cari $[i;j]$ intervalı tamamlanır. Bu interval daxiletmə baxımından maksimaldır: onu nə sola, nə də sağa doğru genişləndirmək mümkün deyil.

Belə hər bir intervala MCBF-3000 maşınının tam olaraq bir dəfə tətbiq edilməsi uyğun gəlir, çünki maşın seçilmiş alt sətirdəki bütün simvolları tərsinə çevirir, bununla da interval daxilindəki bütün uyğunsuzluqları eyni anda düzəldir. Beləliklə, məsələnin cavabı belə maksimal intervalların sayıdır.

Nümunə

Verilmiş nümunə üçün MCBF-3000 maşınının tətbiq edilməli olduğu iki kəsişməyən interval mövcuddur.

Alqoritmin reallaşdırılması

Giriş məlumatlarını oxuyuruq.

cin >> n >> a >> b;

$cnt$ dəyişənində cari uyğunsuzluq intervalının uzunluğunu saxlayırıq. $res$ dəyişənində isə cavabı — maşının tətbiq edilmə sayını toplayırıq.

res = cnt = 0;

Sətirlərin simvollarını ardıcıl olaraq emal edirik.

for (i = 0; i < n; i++)

Əgər a_i \ne b_i olarsa, $cnt$-i bir vahid artırırıq.

  if (a[i] != b[i])
    cnt++;

Əks halda (əgər a_i = b_i olarsa), cari uyğunsuzluq intervalı tamamlanır: $cnt$-i sıfıra sıfırlayırıq və intervalların sayğacı olan $res$-i bir vahid artırırıq.

  else
  {
    if (cnt > 0) res++;
    cnt = 0;
  }

Əgər cnt > 0 olarsa, bu o deməkdir ki, sətrin sonunda tamamlanmamış uyğunsuzluq intervalı qalıb, onun üçün də maşının bir dəfə tətbiq edilməsi lazımdır.

if (cnt > 0) res++;

Cavabı çap edirik.

cout << res << endl;

Python reallaşdırılması

Giriş məlumatlarını oxuyuruq.

n = int(input())
a = input()
b = input()

$cnt$ dəyişənində cari uyğunsuzluq intervalının uzunluğunu saxlayırıq. $res$ dəyişənində isə cavabı — maşının tətbiq edilmə sayını toplayırıq.

res = cnt = 0

Sətirlərin simvollarını ardıcıl olaraq emal edirik.

for i in range(n):

Əgər a_i \ne b_i olarsa, $cnt$-i bir vahid artırırıq.

  if a[i] != b[i]: cnt += 1

Əks halda (əgər a_i = b_i olarsa), cari uyğunsuzluq intervalı tamamlanır: $cnt$-i sıfıra sıfırlayırıq və intervalların sayğacı olan $res$-i bir vahid artırırıq.

  else:
    if cnt > 0: res += 1
    cnt = 0

Əgər cnt > 0 olarsa, bu o deməkdir ki, sətrin sonunda tamamlanmamış uyğunsuzluq intervalı qalıb, onun üçün də maşının bir dəfə tətbiq edilməsi lazımdır.

if cnt > 0: res += 1

Cavabı çap edirik.

print(res)