Pagini recente » Cod sursa (job #1402823) | Cod sursa (job #939507) | Cod sursa (job #1202873) | Cod sursa (job #1712371) | Cod sursa (job #2311693)
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 2000005
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
string patern;
string text;
int longestPrefixSufix[NMAX];
vector<int> result;
void ComputeLongestPrefixSufixArray()
{
int len = 0;
longestPrefixSufix[0] = 0;
for(int i = 1; i < patern.length();++i)
{
while(len > 0 && patern[len] != patern[i])
len = longestPrefixSufix[len-1];
if(patern[len] == patern[i])
len++;
longestPrefixSufix[i] = len;
}
}
void KMP()
{
for(int i = 0, j = 0; i < text.length();)
{
if(patern[j] == text[i])
{
j++;
i++;
if(j == patern.length())
{
result.push_back(i-j);
j = longestPrefixSufix[j-1];
}
}
else if(patern[j] != text[i])
{
if(j == 0)
i++;
else if(j != 0)
{
j = longestPrefixSufix[j - 1];
}
}
}
}
int main()
{
getline(fi,patern);
getline(fi, text);
ComputeLongestPrefixSufixArray();
KMP();
fo<<result.size();
fo<<"\n";
int k = 0;
for(auto y:result)
{
if(k == 1000)
break;
fo<<y<<" ";
k++;
}
}