Cod sursa(job #646190)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 11 decembrie 2011 04:07:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<cstdio>
#include<vector>
#include<list>
#define Check() if (++poz == 8192){fread (buff, 1, 8192, stdin); poz = 0;}
using namespace std;

list <int> :: iterator it, it2; 
list <int> m;
vector <int> sol;
vector <char> a, b;
char buff[8192];
int poz;

void Read(vector <char> &v){
	if (buff[poz] == '\n') Check();
	while (buff[poz] != '\n'){
		v.push_back(buff[poz]);
		Check();
	}
}

int main(){
	freopen ("strmatch.in", "r", stdin), freopen("strmatch.out", "w", stdout);
	int i, j;
	fread (buff, 1, 8192, stdin);
	Read(a);	Read(b);
	
	for (j = 0; j < (int)b.size(); j++){
		for (it = it2 = m.begin(); it != m.end(); it = it2){
			++it2;
			if (a[*it] == b[j]){
				if (++ (*it) == (int)a.size()) {
					sol.push_back(j - a.size() + 1);
					m.erase(it);
				}
			}
			else m.erase(it);
		}
		if (b[j] == a[0]) m.push_back(1);
		}
		
	printf ("%d\n", sol.size());
	for (i = 0; i < (int)sol.size() && i < 1000; i++) 
		printf("%d ", sol[i]);
	return 0;
}