本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden]

1318. F. Magnetic Strip


Description

While playing with the magnetic strips that came with his mini whiteboard, Gabe realized that the strips were made from several equal length bands of positive or negative magnets with no particular order. The strips are only magnetic on one side and Gabe enjoys folding them and trying to hold them together by matching positive bands with negative bands.

The Problem:
In order to make the strongest bond, Gabe would like to know the largest contiguous section on a strip that can be perfectly paired with another section on the same strip. Gabe will fold the strip exactly once to pair the bands. Folding can be done both in between bands and on the center of a band. More specifically, if the folding occurs in between band k and band k+1, after folding band k+1 will be paired with band k, band k+2 will be paired with band k-1, etc. If folding occurs on the center of band k, after folding band k+1 will be paired with band k-1, band k+2 will be paired with band k-2, etc.

Input

The input consists of one line, a string of ‘+’ and ‘-’ characters denoting positive and negative bands on the magnetic strip. The length of this string is at least 1 and no more than 105.

Output

On a line by itself, output the maximum length contiguous section that can be paired with another section on the same strip with a single fold. Note that maximum contiguous section can start on any band of the folded strip, i.e., it may not start at the beginning of the strip or at the folded spot.

Samples

Input Copy
++

Output
0

Hint

Explanation for the second Sample Input/Output: we fold between band 4 and band 5 so, after folding (flipping) the right-hand side over the left-hand side, we’ll have:
-+-
++-+
Explanation for the third Sample Input/Output: we fold between band 10 and band 11 so, after folding (flipping) the right-hand side over the left-hand side, we’ll have:
+++---+++-
+--+++----
Explanation for the last Sample Input/Output: we fold at the center of band 3 so, after folding (flipping) the right-hand side over the left-hand side, we’ll have:
+-*
-+*
Note: we have used ‘*’ to indicate the folded band 3. 

Source

UCF2018 PRACTICE
Problem Information

Time Limit: 5000MS (C/C++,Others×2)
Memory Limit: 256MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 1 / 1
Tags:
Contests involved

1035. UCF 2018 Practice
My history solutions

You didn't submit any solution!
Submit your solution

Login Register