Pagini recente » Cod sursa (job #2176704) | Cod sursa (job #2369887) | Cod sursa (job #2033384) | Cod sursa (job #2075728) | Cod sursa (job #2365936)
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
int N, M;
int longestPrefixSuffix[2000005];
char patern[2000005];
char str[2000005];
vector<int> rez;
void ComputeLPS()
{
int len = 0;
longestPrefixSuffix[0] = 0;
for(int i = 1; i < M;)
{
if(patern[len] == patern[i])
{
len++;
longestPrefixSuffix[i] = len;
i++;
}
else
{
if(len != 0)
len = longestPrefixSuffix[len - 1];
else
{
longestPrefixSuffix[i] = 0;
++i;
}
}
}
}
int main()
{
fi >> (patern);
fi.get();
fi >> (str);
N = strlen((str));
M = strlen((patern));
ComputeLPS();
for(int i = 0, j = 0; i < N;)
{
if(patern[j] == str[i])
{
i ++;
j ++;
if(j == M)
{
rez.push_back(i - j);
j = longestPrefixSuffix[j - 1];
}
}
else
{
if(j == 0)
i++;
else
j = longestPrefixSuffix[j - 1];
}
}
fo << rez.size()<<"\n";
for(auto y : rez)
{
fo << y <<" ";
}
}