如题= =自用模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) {
		FastScanner sc=new FastScanner();
		PrintWriter pw=new PrintWriter(System.out);
		Manacher m=new Manacher();
		char[]c=new char[26];
		for(int i=0;i<26;i++)c[i]=(char)('a'+i);
		while(sc.hasNext()){
			String a=sc.next();
			String s=sc.next();
			m.makep(s);
			if(m.maxlen-1<2){
				pw.println("No solution!");
			}else{
				pw.println(m.start+" "+m.end);
				int py='a'-a.charAt(0);
				for(int i=m.start;i<=m.end;i++){
					int num=s.charAt(i)-'a';
					pw.print(c[(num+py+26)%26]);
				}
				pw.println();
				//pw.println(s.substring(m.start, m.end+1));
			}
			pw.flush();
		}

	}
}
class Manacher{
	int maxn=400050;//2倍字符串长度
	int[]p;
	char[]ns;
	int maxlen;
	int maxpoint;
	int start;
	int end;
	Manacher(){
		p=new int[maxn];
		ns=new char[maxn];
	}
	/*p[i]表示以i为中心在新字符串中最长的回文子串半径    p[i]-1是真实的回文子串长度
	 * maxlen-1是最长回文子串长度*/
	void makep(String s){
		ns[0]='$';ns[1]='#';
		start=-1;
		end=-1;
		int count=2;
		for(int i=0;i<s.length();i++){
			ns[count++]=s.charAt(i);
			ns[count++]='#';
		}
		maxlen=0;
		maxpoint=0;
		int mx=0;
		int id=0;
		for(int i=1;i<count;i++){
			p[i]=mx>i?Math.min(p[2*id-i], mx-i):1;//只有当mx>i且p[2*id-i]<mx-i时p[i]=p[2*id-i] 其他还需要在下面的while继续匹配
			while(i-p[i]>=0&&i+p[i]<count&&ns[i+p[i]]==ns[i-p[i]])++p[i];
			if(mx<i+p[i]){
				mx=i+p[i];
				id=i;
			}
			if(maxlen<p[i]){
				maxlen=p[i];
				maxpoint=i;
				if(p[i]-1>=2){ 			/*这里是算长度大于2的回文串的起始和末尾位置*/
					start=(i-maxlen)/2;
					end=(start+maxlen-1-1);
				}
			}
		}	
	}
}