Java7 の Fork/Join を使ったしりとりと、普通の再帰を使ったしりとりです。

AbstractShiritori.java

package jp.chiheisen.shiritori.impl;

import java.util.Collection;
import java.util.List;

import jp.chiheisen.shiritori.Shiritori;

public abstract class AbstractShiritori implements Shiritori{

	@Override
	public abstract List<String> computeLongestShiritori(String start, Collection<String> words);

	/**
	 * 単語がつながっているか (前の単語の最後の文字と、次の単語の最初の文字が同じか) 判定します。
	 * 
	 * @param prev 前の単語
	 * @param next 次の単語
	 * @return 単語がつながっていれば true, 違うなら false
	 */
	protected boolean isChain(String prev, String next){
		return prev.codePointAt(prev.length() - 1) == next.codePointAt(0);
	}
}

ForkJoinShiritori.java

package jp.chiheisen.shiritori.impl;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.Objects;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

/**
 * Fork/Joinを使ってしりとりを行います。
 * 
 * @author YujiYamamoto
 */
public class ForkJoinShiritori extends AbstractShiritori {
	
	@Override
	public List<String> computeLongestShiritori(String start, Collection<String> words) {
		Objects.requireNonNull(start, "start");
		Objects.requireNonNull(words, "words");
		
		ForkJoinPool pool = new ForkJoinPool();
		ShiritoriTask task = new ShiritoriTask(start, words, 0);
		
		return pool.invoke(task);
	}
	
	private class ShiritoriTask extends RecursiveTask<List<String>>{
		private static final long serialVersionUID = 1L;
		
		private final String prevWord;
		private final Collection<String> words;
		private final int depth;
				
		public ShiritoriTask(String prevWord, Collection<String> words, int depth){
			this.prevWord = prevWord;
			this.words = words;
			this.depth = depth;
		}
		
		@Override
		protected List<String> compute() {
			// 前回の単語はもう使えないので、単語集から取り除く
			List<String> nextWords = new ArrayList<>(words);
			nextWords.remove(prevWord);
			
			List<ShiritoriTask> taskList = new ArrayList<>();
			for(String nextWord : nextWords){
				if(!isChain(prevWord, nextWord)){
					// しりとり不成立
					continue;
				}

				ShiritoriTask task = new ShiritoriTask(nextWord, nextWords, depth + 1);
				if(depth < 2){
					// 並列処理
					task.fork();
				}else{
					// 直列処理 （再帰）
					task.invoke();
				}
				taskList.add(task);
			}

			// 結果取得
			List<String> longest = new ArrayList<>();
			for(ShiritoriTask task : taskList){
				List<String> result = task.join();
				if(longest.size() < result.size()){
					longest = result;
				}
			}
			
			// 前回の単語を、先頭に加える
			longest.add(0, prevWord);
	
			return longest;
		}
	}
}

name.txt

佐藤
中野
杉本
吉岡
鈴木
原田
新井
浅野
高橋
小野
古川
大久保
田中
田村
小松
荒木
伊藤
竹内
市川
野田
渡辺
金子
高野
川村
山本
中山
菊池
星野
中村
和田
水野
望月
小林
石田
島田
大谷
加藤
上田
桜井
堀
吉田
森田
吉川
尾崎
山田
原
山内
黒田
佐々木
工藤
五十嵐
菅野
山口
酒井
西田
永田
松本
横山
西川
内藤
井上
柴田
北村
松村
木村
宮崎
東
西山
林
宮本
安田
田辺
斎藤
内田
中田
広瀬
清水
高木
川口
大島
山崎
安藤
平田
本間
阿部
谷口
久保田
平井
森
丸山
川崎
片山
池田
大野
本田
岩本
橋本
今井
飯田
大石
山下
高田
関
早川
石川
河野
浜田
岡崎
中島
藤本
辻
鎌田
前田
武田
土屋
成田
藤田
杉山
樋口
横田
後藤
上野
吉村
荒井
小川
菅原
川上
小田
岡田
村田
田口
宮田
長谷川
小島
服部
須藤
村上
増田
岩田
篠原
近藤
千葉
中西
石橋
石井
小山
山中
萩原
遠藤
平野
福島
高山
斉藤
大塚
永井
松原
坂本
久保
松岡
栗原
青木
松井
森本
伊東
藤井
渡部
矢野
南
西村
岩崎
秋山
桑原
福田
木下
石原
小西
太田
佐野
松下
大森
三浦
菊地
大橋
三宅
藤原
野口
馬場
沢田
松田
松尾
熊谷
福井
岡本
野村
松浦
奥村
中川
大西
小池
岡
内山
関根
中沢
榊原
片岡
塚本
津田
藤川
松永
山根
三好
大内
関口
神田
岡野
竹中
北川
佐久間
金井
庄司
上原
前川
甲斐
川原
奥田
植田
米田
藤沢
上村
田島
黒木
吉原
吉野
安部
松山
松島
今村
中井
落合
塚田
八木
宮川
佐伯
吉本
富田
白井
西岡
藤岡
白石
岡部
金田
竹下
小泉
長田
堤
下田
牧野
大川
堀田
藤村
小沢
堀内
山岸
宮内
小野寺
畠山
野崎
安井
平山
浅井
岩井
竹本
岡村
及川
泉
谷川
河合
谷
町田
栗田
古賀
若林
西野
広田
中尾
神谷
新田
窪田
川島
松崎
古田
福本
坂口
稲垣
徳永
小谷
寺田
細川
土田
石黒

RecursiveShiritori.java

package jp.chiheisen.shiritori.impl;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.Objects;

/**
 * 再帰を使ってしりとりを行います。
 * 
 * @author YujiYamamoto
 */
public class RecursiveShiritori extends AbstractShiritori {

	@Override
	public List<String> computeLongestShiritori(String prevWord, Collection<String> words){
		Objects.requireNonNull(prevWord, "prevWord");
		Objects.requireNonNull(words, "words");

		// 前回の単語はもう使えないので、単語集から取り除く
		List<String> nextWords = new ArrayList<>(words);
		nextWords.remove(prevWord);
		
		List<String> longest = new ArrayList<>();
		for(String nextWord : nextWords){
			if(!isChain(prevWord, nextWord)){
				// しりとり不成立
				continue;
			}

			// 再帰
			List<String> result = computeLongestShiritori(nextWord, nextWords);
			if(longest.size() < result.size()){
				longest = result;
			}
		}

		// 前回の単語を、先頭に加える
		longest.add(0, prevWord);

		return longest;
	}
}

Shiritori.java

package jp.chiheisen.shiritori;

import java.util.Collection;
import java.util.List;

public interface Shiritori {
	
	/**
	 * 指定された単語を使ってしりとりを行い、最も長く続いた結果を返します。
	 * 
	 * @param start 最初の単語
	 * @param words 単語集
	 * @return 最も長く続いたしりとり
	 */
	public List<String> computeLongestShiritori(String start, Collection<String> words);
}

ShiritoriSpeedTest.java

package jp.chiheisen.shiritori;

import static org.hamcrest.core.Is.is;
import static org.junit.Assert.assertThat;

import java.io.IOException;
import java.nio.charset.Charset;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;

import jp.chiheisen.shiritori.impl.ForkJoinShiritori;
import jp.chiheisen.shiritori.impl.RecursiveShiritori;

import org.junit.Test;

public class ShiritoriSpeedTest {
	
	@Test
	public void testRecursiveSpeed() throws IOException{
		testSpeed(new RecursiveShiritori());
	}
	
	@Test
	public void testForkJoinSpeed() throws IOException{
		testSpeed(new ForkJoinShiritori());
	}
	
	private void testSpeed(Shiritori shiritori) throws IOException{
		Collection<String> words = Files.readAllLines(Paths.get("name.txt"), Charset.forName("UTF-8"));
		List<String> result = shiritori.computeLongestShiritori("佐藤", words);
		
		assertChain(result);
		System.out.println(result);
	}
	
	private void assertChain(List<String> list){
		Iterator<String> ite = list.listIterator();
		String prev = ite.next();
		while(ite.hasNext()){
			String next = ite.next();
			assertThat(prev.codePointAt(prev.length() - 1), is(next.codePointAt(0)));
			prev = next;
		}
	}
}