Pagini recente » Cod sursa (job #953448) | Cod sursa (job #132527) | Cod sursa (job #2139883) | Rating Dragoiu Raul Ioan (RaulDragoiu) | Cod sursa (job #1810909)
#include <iostream>
#include <fstream>
#include <math.h>
#include <string.h>
using namespace std;
int p[2000000],mereti,meretj;
string text,s;
int counter, solve[1001];
void create_temporary_array(string s,int p[])
{
int j = 0, i = 1, meret = s.size();
while(i < meret)
{
if(s[j] == s[i])
{
p[i] = j + 1;
i++;
j++;
}
else
{
while(j != 0 and s[j] != s[i])
{
j = p[j-1];
}
p[i] = j + (s[j] == s[i]);
if(s[i] == s[j])
j++;
i++;
}
}
}
int main()
{
ifstream be("strmatch.in");
ofstream ki("strmatch.out");
getline(be,s);
getline(be,text);
create_temporary_array(s,p);
mereti = text.size();
meretj = s.size();
int i = 0, j = 0;
/*for(int i = 0;i < s.size();i++)
{
ki<<p[i]<<" ";
}
ki<<endl;
ki<<text.substr(1081,s.size())<<endl;
ki<<s<<endl;*/
while( i < mereti)
{
if(text[i] == s[j])
{
if(j == 0)
{
//ki<<i<<" == C"<<endl;
}
i++;
j++;
}
else
{
if(j == 0)
{
i++;
}
j = p[j-1];
//ki<<j<<endl;
}
if(j == meretj)
{
if(counter < 1000)
solve[counter] = i - j;
counter++;
j = p[j-1];
//ki<<"NEW J = "<<j<<" I = "<<i<<endl;
}
}
ki<<counter<<endl;
short woohoo = min(1000,counter);
for(int i = 0;i<woohoo;i++)
{
ki<<solve[i]<<" ";
}
return 0;
}