Cod sursa(job #1154900)

Utilizator nickulNic Kul nickul Data 26 martie 2014 14:23:29
Problema Potrivirea sirurilor Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<fstream>
#include<string>
#include<vector>
 
using namespace std;
 
ifstream in("strmatch.in");
ofstream out("strmatch.out");
 
int main()
{
    string m,n,s;
    vector<int> b;
    in>>m>>n;
    int M=m.length(),N=n.length(),i=M,j=M,a=0;
	while(i!=-1)
	{
		i=m.rfind(m.at(M-1),i-2)+1;
		if(i!=-1&&m.substr(0,i)==m.substr(M-i))
		{
			j=M-i;
			break;
		}
	}
	s=m.substr(M-j);
	i=n.find(m);
	b.push_back(i),a++;
    while(i!=-1)
    {
		i+=j;
		if(j!=M)
		{
			i=n.find(m,i);
			if(b.size()<1001) b.push_back(i);
			a++;
			while(i!=-1&&n.find(s,i+M)==i+M)
			{
				i+=j;
				if(b.size()<1001) b.push_back(i);
				a++;
			}
		}
		else
		{
			i=n.find(m.at(j-1),i+j-1);
			if(i!=-1) i-=j,i=n.find(m,i);
			if(b.size()<1001) b.push_back(i);
			a++;
			while(i!=-1&&n.find(s,i+M)==i+M)
			{
				i+=j;
				if(b.size()<1001) b.push_back(i);
				a++;
			}
		}
	}
	b.pop_back();
	a--;
    out<<a<<'\n';
    for(i=0;i<b.size();i++) out<<b.at(i)<<" ";
}