Pagini recente » Cod sursa (job #2524951) | Cod sursa (job #2853809) | Cod sursa (job #460100) | Cod sursa (job #1615006) | Cod sursa (job #2311632)
#include <bits/stdc++.h>
#define NMAX 2000005
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
char patern[NMAX];
char text[NMAX];
int longestPrefixSufix[NMAX];
vector<int> result;
int N,M;
void ComputeLongestPrefixSufixArray()
{
int len = 0;
longestPrefixSufix[0] = 0;
longestPrefixSufix[1] = 0;
for(int i = 2; i <= M; ++i)
{
while(len > 0 && patern[len+1] != patern[i])
len = longestPrefixSufix[len];
if(patern[len+1] == patern[i])
len++;
longestPrefixSufix[i] = len;
}
}
void KMP()
{
for(int i = 0, j = 0; i <= N;++i)
{
while( j > 0 && patern[j+1] !=text[i])
j = longestPrefixSufix[j];
if(patern[j+1] == text[i])
j++;
if(j == M)
{
result.push_back(i-j);
j = longestPrefixSufix[j];
}
}
}
int main()
{
fi>>(patern+1);
fi>>(text+1);
fi.close();
N = strlen(text+1);
M = strlen(patern+1);
ComputeLongestPrefixSufixArray();
KMP();
fo<<result.size();
fo<<"\n";
for(auto y:result)
fo<<y<<" ";
fo.close();
}