AkariDaisukiDiv1.cpp

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <climits>
#include <cstring>
using namespace std;

typedef long long  int64;
typedef vector<int> vi;
typedef string ST;
typedef stringstream SS;
typedef vector< vector <int> > vvi;
typedef pair<int,int> ii;
typedef vector <string> vs;

#define Pf	printf
#define	Sf	scanf

#define	ep	1e-9
#define PI M_PI
#define E M_E

#define	CL(a, b)	memset(a, b, sizeof(a))
#define	mp	make_pair

#define	pb	push_back

#define	all(c)	(c).begin(), (c).end()
#define	tr(i, c)	for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)

#define	present(x, c)	((c).find(x) != (c).end())		//map & set//
#define	cpresent(x, c)	(find(all(c),x) != (c).end())	//vector & list//

#define forn(i, n)	for(int i = 0, loop_ends_here = (int)n; i < loop_ends_here; i++)
#define forab(i, a, b)	for(int i = a, loop_ends_here = (int) b; i <= loop_ends_here; i++)
#define rep(i, a, b)	for(int i = a, loop_ends_here = (int)b; i>=loop_ends_here; i--)

#define read(n)		scanf("%d", &n)
#define write(n)	printf("%d ", n)
#define writeln(n)	printf("%d\n", n)


class AkariDaisukiDiv1
{
public:
	int countF(string Waai, string Akari, string Daisuki, string S, string F, int k)
	{
		int ret;
		
		return ret;
	}
};

// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit 2.1.8 (beta) modified by pivanof
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool KawigiEdit_RunTest(int testNum, string p0, string p1, string p2, string p3, string p4, int p5, bool hasAnswer, int p6) {
	cout << "Test " << testNum << ": [" << "\"" << p0 << "\"" << "," << "\"" << p1 << "\"" << "," << "\"" << p2 << "\"" << "," << "\"" << p3 << "\"" << "," << "\"" << p4 << "\"" << "," << p5;
	cout << "]" << endl;
	AkariDaisukiDiv1 *obj;
	int answer;
	obj = new AkariDaisukiDiv1();
	clock_t startTime = clock();
	answer = obj->countF(p0, p1, p2, p3, p4, p5);
	clock_t endTime = clock();
	delete obj;
	bool res;
	res = true;
	cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
	if (hasAnswer) {
		cout << "Desired answer:" << endl;
		cout << "\t" << p6 << endl;
	}
	cout << "Your answer:" << endl;
	cout << "\t" << answer << endl;
	if (hasAnswer) {
		res = answer == p6;
	}
	if (!res) {
		cout << "DOESN'T MATCH!!!!" << endl;
	} else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {
		cout << "FAIL the timeout" << endl;
		res = false;
	} else if (hasAnswer) {
		cout << "Match :-)" << endl;
	} else {
		cout << "OK, but is it right?" << endl;
	}
	cout << "" << endl;
	return res;
}
int main() {
	bool all_right;
	all_right = true;
	
	string p0;
	string p1;
	string p2;
	string p3;
	string p4;
	int p5;
	int p6;
	
	{
	// ----- test 0 -----
	p0 = "a";
	p1 = "b";
	p2 = "c";
	p3 = "x";
	p4 = "axb";
	p5 = 2;
	p6 = 2;
	all_right = KawigiEdit_RunTest(0, p0, p1, p2, p3, p4, p5, true, p6) && all_right;
	// ------------------
	}
	
	{
	// ----- test 1 -----
	p0 = "a";
	p1 = "b";
	p2 = "c";
	p3 = "x";
	p4 = "abcdefghij";
	p5 = 1;
	p6 = 0;
	all_right = KawigiEdit_RunTest(1, p0, p1, p2, p3, p4, p5, true, p6) && all_right;
	// ------------------
	}
	
	{
	// ----- test 2 -----
	p0 = "a";
	p1 = "a";
	p2 = "a";
	p3 = "b";
	p4 = "aba";
	p5 = 2;
	p6 = 4;
	all_right = KawigiEdit_RunTest(2, p0, p1, p2, p3, p4, p5, true, p6) && all_right;
	// ------------------
	}
	
	{
	// ----- test 3 -----
	p0 = "a";
	p1 = "b";
	p2 = "c";
	p3 = "d";
	p4 = "baadbdcbadbdccccbaaaadbdcbadbdccbaadbdcba";
	p5 = 58;
	p6 = 191690599;
	all_right = KawigiEdit_RunTest(3, p0, p1, p2, p3, p4, p5, true, p6) && all_right;
	// ------------------
	}
	
	{
	// ----- test 4 -----
	p0 = "a";
	p1 = "x";
	p2 = "y";
	p3 = "b";
	p4 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
	p5 = 49;
	p6 = 1;
	all_right = KawigiEdit_RunTest(4, p0, p1, p2, p3, p4, p5, true, p6) && all_right;
	// ------------------
	}
	
	{
	// ----- test 5 -----
	p0 = "waai";
	p1 = "akari";
	p2 = "daisuki";
	p3 = "usushio";
	p4 = "id";
	p5 = 10000000;
	p6 = 127859200;
	all_right = KawigiEdit_RunTest(5, p0, p1, p2, p3, p4, p5, true, p6) && all_right;
	// ------------------
	}
	
	{
	// ----- test 6 -----
	p0 = "vfsebgjfyfgerkqlr";
	p1 = "ezbiwls";
	p2 = "kjerx";
	p3 = "jbmjvaawoxycfndukrjfg";
	p4 = "bgjfyfgerkqlrvfsebgjfyfgerkqlrvfsebgjfyfgerkqlrvfs";
	p5 = 1575724;
	p6 = 483599313;
	all_right = KawigiEdit_RunTest(6, p0, p1, p2, p3, p4, p5, true, p6) && all_right;
	// ------------------
	}
	
	if (all_right) {
		cout << "You're a stud (at least on the example cases)!" << endl;
	} else {
		cout << "Some of the test cases had errors." << endl;
	}
	return 0;
}
// PROBLEM STATEMENT
// 
// Consider the following function:
// f(X) = Waai + X + Akari + X + Daisuki
// Here, X is a string and + denotes string concatenation.
// Waai, Akari and Daisuki are constant non-empty strings.
// 
// 
// 
// You are given 5 strings Waai, Akari, Daisuki, S and F, and a  int k. 
// Compute how many times F occurs in f^k(S) as its substring. (The notation f^k(S) means that f is applied to S exactly k times in a row. See Notes for a formal definition.) Since the number can be quite large, compute the number modulo 1,000,000,007.
// 
// 
// DEFINITION
// Class:AkariDaisukiDiv1
// Method:countF
// Parameters:string, string, string, string, string, int
// Returns:int
// Method signature:int countF(string Waai, string Akari, string Daisuki, string S, string F, int k)
// 
// 
// NOTES
// -Formally, we have f^1(X)=f(X) and for k greater than one we have f^k(X)=f(f^(k-1)(X)).
// -String A is substring of B if A can be obtained by erasing some (possibly zero) characters from the beginning of B and some (possibly zero) characters from the end of B.
// 
// 
// CONSTRAINTS
// -Waai, Akari, Daisuki, S, and F will contain between 1 and 50 characters, inclusive.
// -Each character of Waai, Akari, Daisuki, S, and F will be a lowercase letter ('a'-'z').
// -k will be between 1 and 10,000,000, inclusive.
// 
// 
// EXAMPLES
// 
// 0)
// "a"
// "b"
// "c"
// "x"
// "axb"
// 2
// 
// Returns: 2
// 
// S = "x",
// f(S) = "axbxc",
// f^2(S) = f("axbxc") = "aaxbxcbaxbxcc".
// This string contains the substring "axb" twice.
// 
// 1)
// "a"
// "b"
// "c"
// "x"
// "abcdefghij"
// 1
// 
// Returns: 0
// 
// The answer can be zero.
// 
// 2)
// "a"
// "a"
// "a"
// "b"
// "aba"
// 2
// 
// Returns: 4
// 
// S = "b",
// f(S) = "ababa",
// f^2(S) = f("ababa") = "aababaaababaa".
// This string contains the substring "aba" four times. You must count overlapping substrings.
// 
// 3)
// "a"
// "b"
// "c"
// "d"
// "baadbdcbadbdccccbaaaadbdcbadbdccbaadbdcba"
// 58
// 
// Returns: 191690599
// 
// 
// 
// 4)
// "a"
// "x"
// "y"
// "b"
// "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
// 49
// 
// Returns: 1
// 
// 
// 
// 5)
// "waai"
// "akari"
// "daisuki"
// "usushio"
// "id"
// 10000000
// 
// Returns: 127859200
// 
// 
// 
// 6)
// "vfsebgjfyfgerkqlr"
// "ezbiwls"
// "kjerx"
// "jbmjvaawoxycfndukrjfg"
// "bgjfyfgerkqlrvfsebgjfyfgerkqlrvfsebgjfyfgerkqlrvfs"
// 1575724
// 
// Returns: 483599313
// 
// END KAWIGIEDIT TESTING




//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!