글 읽기 - 데이터를 추가해주세요.

willook 4년 전 0

잘못된 풀이가 통과됩니다.

https://www.acmicpc.net/source/15114572

입력

ABABCABABABCABABAB

ABABCABABAB

정답

1 8

오답

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int[] preprocess(char[] p) {
		int n = p.length;
		int[] parr = new int[n];
		boolean isSame = true;
		for(int i=1;i<n;i++) {
			int j = parr[i-1];
			if(p[i] == p[j]) {
				parr[i] = j+1;
				if(j!=0 && i < n && p[i] != p[i-1])
					isSame = false;
			}
			else {
				if(isSame && p[i] == p[i-1]) parr[i] = j;
				else if(p[i] == p[0])
					parr[i] = 1;
				else
					parr[i] = 0;
				isSame = true;
			}
		}
		return parr;
	}
	static int solve(char[] t, char[] p) {
		int n = t.length;
		int m = p.length;
		int[] parr = preprocess(p);
		int ret = 0;
		for(int i=0,j=0;i<n;i++) {
			if(t[i] == p[j])
				j+=1;
			else {
				j = j==0 ? 0 : parr[j-1];
				if(t[i] == p[j])
					j+=1;
			}
			if(j==m) {
				ret+=1;
				sb.append(i-j+2).append(' ');
				j=parr[j-1];
			}
		}
		sb.append('\n');
		return ret;
	
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		char[] t = br.readLine().toCharArray();
		char[] p = br.readLine().toCharArray();
		int ret = solve(t, p);
		bw.write(ret+"\n");
		bw.write(sb.toString());
		bw.flush();
	}
}

startlink 4년 전 0

재채점했습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

데이터를 추가해주세요.

willook 4년 전 0

startlink 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말