Pagini recente » Cod sursa (job #313433) | Cod sursa (job #2704339) | Cod sursa (job #1830099) | Cod sursa (job #1047193) | Cod sursa (job #2716496)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int N = 2e6;
char pattern[N+1],txt[N+1];
int lps[N+1]; /// longest prefix that is also sufix (in pattern)
vector <int> pos;
void calculateLPS(int m)
{
int len = 0;
lps[0] = 0;
int i=1;
while(i < m)
{
if(pattern[i]==pattern[len])
{
++len;
lps[i] = len;
++i;
}
else{
if(len!=0){
len = lps[len-1];
}
else
{
lps[i] = 0;
++i;
}
}
}
}
void KmpSearch(char *pattern, char *txt){
int n = strlen(txt);
int m = strlen(pattern);
calculateLPS(m);
int i=0,j=0;
while(i<n)
{
if(pattern[j] == txt[i])
{
++i;
++j;
}
if(j==m)
{
pos.push_back(i-m);
j = lps[j-1];
}
else if(i<n && pattern[j] != txt[i])
{
if(j!=0)
{
j = lps[j-1];
}
else{
++i;
}
}
}
}
int main()
{
in>>pattern>>txt;
KmpSearch(pattern,txt);
out<<pos.size()<<'\n';
for(auto &i : pos)
out<<i<<' ';
return 0;
}