Cod sursa(job #300572)

Utilizator HaggisRanca Razvan Haggis Data 7 aprilie 2009 15:23:18
Problema Potrivirea sirurilor Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<fstream>
#include<vector>
#include<string>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char a[2000007], b[2000007];

int i,j,m[2000010],nrsol;
vector<int> sol;

void kmppre()
{
	i=0;
	j=-1;
	m[i]=j;
	int l2=strlen(a);
	while(i<=l2)
	{
		if(j>=0 && a[i]!=a[j])
			j=m[j];
		++i;
		++j;
		m[i]=j;
	}
}

void kmpmain()
{
	int l1=strlen(b);
	int l2=strlen(a);
	i=0;
	j=0;
	while(i+j<=l1)
		{
			if(b[i+j]==a[j])
				{
					++j;
					if(j==l2)
					{
						++nrsol;
						if(nrsol<=1000)
							sol.push_back(i);
						
					}
				}
			else{
				i=i+j-m[j];
				if(j>0)
					j=m[j];
				}
		}
}

int main ()
{
	
	in.get(a, 2000003);
	in.get();
	in.get(b, 2000003);
	kmppre();
	kmpmain();
	out<<nrsol<<"\n";
	if(!sol.empty())
	for(i=0;i<sol.size();i++)
		out<<sol[i]<<" ";
		
	return 0;
}