Pagini recente » Cod sursa (job #2572893) | Cod sursa (job #1181645) | Cod sursa (job #1392914) | Monitorul de evaluare | Cod sursa (job #2204706)
#include<iostream>
#include<fstream>
#include<cstring>
#include<vector>
#define nmax 2000001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[nmax],b[nmax];
int automaton[nmax];
vector<int> pos_holder;
void build_automaton()
{
int j = 0;
int i = 1;
while(i<strlen(a))
{
if(a[i] == a[j])
{
automaton[i] = j+1;
j++;
}
else
{
if(j != 0)
{
j = automaton[j-1];
continue;
}
}
i++;
}
}
int kmp()
{
int j = 0;
int i = 0;
int n_a = 0;
while(i < strlen(b))
{
if(a[j] == b[i])
{
i++;
j++;
}
if(j == strlen(a))
{
n_a++;
if(pos_holder.size() < 1000) pos_holder.push_back(i-strlen(a));
j = automaton[j-1];
}
else if(i < strlen(b) && a[j] != b[i])
{
if(j != 0) j = automaton[j-1];
else i+=1;
}
}
return n_a;
}
int main()
{
fin>>a>>b;
build_automaton();
fout<<kmp()<<"\n";
for(int i=0;i<pos_holder.size();i++)
{
fout<<pos_holder[i]<<" ";
}
}