Pagini recente » Cod sursa (job #94421) | Cod sursa (job #826890) | Cod sursa (job #490993) | Cod sursa (job #2964852) | Cod sursa (job #1495265)
#include <fstream>
#include <cstring>
#define NMAX 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n , m , pi[NMAX] , dp[NMAX] , nr;
char s[NMAX] , c[NMAX];
int main()
{
f >> c + 1 >> s + 1;
n = strlen(s + 1);
m = strlen(c + 1);
pi[1] = 0;
for(int i = 2 ; i <= m ; ++i) {
int k = pi[i - 1];
while(k > 0 && c[i] != c[k + 1]) {
k = pi[k];
}
if(c[i] == c[k + 1]) {
pi[i] = k + 1;
}
else{
pi[i] = 0;
}
}
int k = 0;
for(int i = 1 ; i <= n ; ++i) {
while(k > 0 && s[i] != c[k + 1]) {
k = pi[k];
}
if(s[i] == c[k + 1]) {
++k;
}
dp[i] = k;
}
for(int i = 0 ; i < n ; ++i) {
if(dp[i] == m) {
++nr;
}
}
g << nr << '\n';
nr = 0;
for(int i = 0 ; i < n ; ++i) {
if(dp[i] == m) {
++nr;
g << i - m << " ";
}
if(nr >= 1000){
return 0;
}
}
return 0;
}