Cod sursa(job #1155129)

Utilizator nickulNic Kul nickul Data 26 martie 2014 17:52:43
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<fstream>
#include<string>
#include<vector>
 
using namespace std;
 
ifstream in("strmatch.in");
ofstream out("strmatch.out");
 
int main()
{
    string m,n,p,s;
    vector<int> b,u;
    in>>m>>n;
    int M=m.length(),N=n.length(),i,j=0,a=0;
	u.resize(M);
	u.at(0)=0;
	for(i=1;i<M;i++)
	{
		j=u.at(i-1);
		while(j>0&&m.at(j)!=m.at(i)) j=u.at(j-1);
		if(m.at(j)==m.at(i)) j++;
		u.at(i)=j;
	}
	j=0;
	for(i=0;i<N;i++)
	{
		while(j>0&&m.at(j)!=n.at(i)) j=u.at(j-1);
		if(m.at(j)==n.at(i)) j++;
		if(j==M) 
		{
			j=u.at(j-1);
			a++;
			if(b.size()<1001) b.push_back(i-M+1);
		}
	}
	out<<a<<'\n';
    for(i=0;i<b.size();i++) out<<b.at(i)<<" ";
}