Cod sursa(job #632537)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 11 noiembrie 2011 15:55:28
Problema Potrivirea sirurilor Scor 6
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<stdio.h>
#include<string.h>
#include<vector>
#define N 2000010
using namespace std;

int l,la,ii;
char a[N],b[N];
vector<int> v,rez;

int main() {
	int i=0;
	vector<int>::iterator it;

	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);

	gets(a);
	gets(b);

	l=strlen(b); la=strlen(a);

	for(ii=0;ii<l;++ii) {

		if(!v.empty())
		for(it=v.begin();it!=v.end();++it)
			if(b[ii] == a[*it + 1]) {
				if(++(*it)==la-1) {
					rez.push_back(ii - la + 1);
					v.erase(it);

					if(v.empty())
                        break;
				}
			}
			else {
				v.erase(it);

				if(v.empty())
                    break;
			}

		if(a[0]==b[ii])
			v.push_back(0);
	}

	printf("%d\n",rez.size());

	for(i=0;i!=rez.size();++i)
		printf("%d ",rez[i]);

	return 0;
}