Pagini recente » Cod sursa (job #2527877) | Cod sursa (job #2587211) | Cod sursa (job #1663594) | Cod sursa (job #1609004) | Cod sursa (job #2869978)
#include <fstream>
#include <cstring>
#define maxN 2000001
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
char s1[maxN], s2[maxN];
int Poz[maxN], Nr = 0;
int Lps[maxN];
void Lps_ (char s1[])
{
int l1 = strlen(s1);
int i = 1, j = 0;
Lps[0] = 0;
while(i < l1)
{
if(s1[i] == s1[j]){
j++;
Lps[i] = j;
i++;
}
else{
if(j == 0){
Lps[i] = 0;
i++;
}
else j = Lps[j-1];
}
}
}
void Kmp (char s1[], char s2[])
{
int l1 = strlen(s1), l2 = strlen(s2);
int i = 0, j = 0;
while(i < l2)
{
if(s2[i] == s1[j]) i++, j++;
if(j == l1){
Nr++;
Poz[Nr] = i - j;
j = Lps[j-1];
}
else if(s2[i] != s1[j])
if(j != 0) j = Lps[j-1];
else i++;
}
}
int main()
{
cin.get(s1, maxN);
cin.get();
cin.get(s2 ,maxN);
Lps_(s1);
Kmp(s1, s2);
cout << Nr <<"\n";
for(int i = 1; i <= Nr && i <= 1000; i++)
{
cout << Poz[i] << " ";
}
return 0;
}