Pagini recente » Cod sursa (job #2532565) | Cod sursa (job #2082810)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#define Nmax 2000000
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s1,s2;
vector<int> v1;
int vec[Nmax];
void constuctie(int vec[],int lungime)
{
int ok;
int i=0,j;
for(j=1;j<=lungime;j++)
{
if(s1[i]==s1[j])
{
vec[j]=i+1;
i++;
j++;
}
if(s1[i]!=s1[j]&&i!=0)
{
ok=1;
while(ok&&i!=0)
{
i=vec[i-1];
if(s1[j]==s1[i])
{
vec[j]=i+1;
ok=0;
}
}
if(i==0&&s1[j]==s1[i])
vec[j]=vec[i]+1;
else if(i==0&&s1[j]!=s1[i])
{
vec[j]=0;
}
}
}
}
int main()
{
getline(f,s1);
getline(f,s2);
int lungime=s1.size()-1;
int i=0;
int j=0;
int nr=0;
constuctie(vec,lungime);
for(i=0;i<s2.size();i++)
{
if(s1[j]==s2[i])
{
j++;
//cout<<j<<' ';
if(j==s1.size())
{
nr++;
if(nr<1001)
v1.push_back(i-j+1);
j--;
j=vec[j];
if(i+1<s2.size()&&s1[j]!=s2[i+1])
j=0;
}
}
else if(s1[j]!=s2[i]&&j!=0)
{
if(s1[vec[j]]==s2[i])
j=vec[j]+1;
else if(s1[0]==s2[i])
j=1;
else j=0;
}
}
if(nr!=0)
{
g<<nr<<"\n";
for(int i=0;i<v1.size();i++)
g<<v1[i]<<' ';
}
return 0;
}