Cod sursa(job #1046052)

Utilizator mikeshadowIon Complot mikeshadow Data 2 decembrie 2013 17:09:24
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <string.h>
 
#define min(a,b) ((a<b)?a:b)
#define max(a,b) ((a<b)?b:a)
#define abs(a) ((a<0)?-a:a)
 
#define INF 1000001
 
using namespace std;
 

#ifndef TEST
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
#else
ifstream fin ("input.txt");
ofstream fout ("output.txt");
#endif
 
#define MAXN 2000000

string s,t;

vector<int> sol;

int T[MAXN+1];

void build()
{
	int c = 0;
	T[0] = -1;
	T[1] = 0;
	for (int i=2; i<s.length(); i++)
	{
		if (s[i-1]==s[c])
		{
			c++;
			T[i]=c;
		} else if (c>0)
		{
			c = T[c];
			i--;
		} else T[i]=0;
	}
}

int main()
{
	fin>>s>>t;

	int sl,tl;
	sl = s.length();
	tl = t.length();

	build();

	int c=0,i=0;
	while (i+sl <= tl)
	{
		if (t[i+c]==s[c])
		{
			if (c==sl-1)
			{
				sol.push_back(i);
				i =i+c- T[c];
				if (T[c]>-1)
				c = T[c];
				else c=0;
			}
			else c++;
		} else
		{
			i = i+c -T[c];
			if (T[c]>-1)
				c = T[c];
			else c=0;
		}
	}
 
	fout<<sol.size();
	fout<<'\n';

	for (int i=0; i<sol.size(); i++)
		fout<<sol[i]<<' ';
    return 0;
}