Pagini recente » Cod sursa (job #2325951) | Cod sursa (job #697278) | Cod sursa (job #694402) | Cod sursa (job #3156829) | Cod sursa (job #2903475)
#include <iostream>
#include <fstream>
#include <cstring>
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
int lps[2005000];
char c1[2005000];
char c2[2005000];
int x1;
int x2;
int countt;
int rez[1001];
void find()
{
int i=0,j=0;
while(j<x2)
{
if(c1[i]==c2[j])
i++,j++;
else if(i!=0)
i=lps[i-1];
else
j++;
if(i==x1)
{
if(countt<1000)
rez[countt]=j-i;
countt++;
i=lps[i-1];
}
}
}
void createLps()
{
x1 = strlen(c1);
x2 = strlen(c2);
int i=1;
int len=0;
for (int k = 1; c1[k] != '\0'; k++)
{
do
{
if (c1[len] == c1[k])
break;
else if (len != 0)
len = lps[len - 1];
} while (len != 0);
if (c1[len] == c1[k])
len++;
lps[k] = len;
}
}
int main()
{
fin.getline(c1,2005000);
fin.getline(c2,2005000);
createLps();
//for(int i=0;i<x1;i++)
// std::cout<<lps[i]<<" ";
find();
fout<<countt<<"\n";
for(int i=0;i<countt && i<1000;i++)
fout<< rez[i]<<" ";
}