Cod sursa(job #1676570)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 5 aprilie 2016 23:54:28
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#define NMAX 2000005
#define MOD 666013
#define INF 0x3f3f3f3f
#define pb push_back

using namespace std;

typedef pair<int, int> pii;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char a[NMAX], b[NMAX],n;
vector<int> v;
int pref[NMAX];

void prefix() {
	int i,j=0;

	for(i=2;i<=n;++i) {
		while(j>0 && a[j+1] != a[i])
			j=pref[j];

		if(a[j+1]==a[i]) ++j;

		pref[i]=j;
	}
}

int main() {
	int i,j,m;

	fin>>a+1>>b+1;
	n=strlen(a+1);
	m=strlen(b+1);

	prefix();
	for(i=1,j=0;i<=m;++i) {
		while(j>0 && a[j+1] != b[i])
			j=pref[j];

		if(a[j+1] == b[i]) ++j;

		if(j==n) {
			j=pref[n];
			v.pb(i-n);
		}
	}

	fout<<v.size()<<'\n';
	for(i=0;i<v.size();++i)
		fout<<v[i]<<' ';

    return 0;
}