Cod sursa(job #2301617)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 13 decembrie 2018 11:38:26
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <string>
#include <vector>
#define N 1000000
using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

int main() {
	string A, B; cin >> A >> B;
	int z[N + 1];
	z[0] = 0;
	int st = 0, dr = 0;
	
	for(int i = 1; i < A.size(); i++){
		if (i > dr){
			z[i] = 0;
			while(i + z[i] < A.size() && A[i + z[i]] == A[z[i]])
				z[i]++;
				
			st = i;
			dr = i + z[i] - 1;
		}
		else {
			z[i] = min(z[i - st], dr - i + 1);
			
			if (i + z[i] - 1 == dr){
				while(i + z[i] < A.size() && A[i + z[i]] == A[z[i]])
					z[i]++;
				
				st = i;
				dr = i + z[i] - 1;
			}
		}
	}
	
	st = dr = -1;
	int dp[N + 1];
	vector<int> ans;
	for(int i = 0; i < B.size(); i++){
		if (i > dr){
			dp[i] = 0;
			while(i + dp[i] < B.size() && dp[i] < A.size() && B[i + dp[i]] == A[dp[i]])
				dp[i]++;
				
			st = i;
			dr = i + dp[i] - 1;
		}
		else {
			dp[i] = min(dp[i - st], dr - i + 1);
			
			if (i + dp[i] - 1 == dr){
				while(i + dp[i] < B.size() && dp[i] < A.size() && B[i + dp[i]] == A[dp[i]])
					dp[i]++;
				
				st = i;
				dr = i + dp[i] - 1;
			}
		}
		
		if (dp[i] == A.size()) ans.push_back(i);
	}
	
	cout << ans.size() << endl;
	for(int i = 0; i < ans.size(); i++)
		cout << ans[i] << ' ';
	
	return 0;
}