Pagini recente » Cod sursa (job #507369) | Cod sursa (job #2924228) | Borderou de evaluare (job #367058) | Cod sursa (job #260588) | Cod sursa (job #2311583)
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 2000000
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
string patern;
string text;
int longestPrefixSufix[NMAX];
vector<int> result;
int N,M;
void ComputeLongestPrefixSufixArray()
{
int len = 0;
longestPrefixSufix[0] = 0;
for(int i = 1; i < M;)
{
if(patern[len] == patern[i])
{
len++;
longestPrefixSufix[i] = len;
i++;
}
else if(patern[len] != patern[i])
{
if(len != 0)
len = longestPrefixSufix[len - 1];
else if(len == 0)
{
longestPrefixSufix[i] = 0;
i++;
}
}
}
}
void KMP()
{
for(int i = 0, j = 0; i <= N;)
{
if(patern[j] == text[i])
{
j++;
i++;
if(j == M)
{
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);
N = text.length();
M = patern.length();
ComputeLongestPrefixSufixArray();
KMP();
fo<<result.size();
fo<<"\n";
for(auto y:result)
fo<<y<<" ";
}